Packet-Layer Transparent Packet-Switching Network

• US 20090310610A1
• Filed: 02/20/2009
• Published: 12/17/2009
• Est. Priority Date: 06/12/2008
• Status: Active Grant

• Current Assignee: Mark Sandtrom
• Original Assignee: Optimum Communications Services, Inc.
• Inventors: Sandstrom, Mark Henrik
• Granted Patent: US 8,619,769 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• 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/34 Source routing
• CPC Class Codes: H04L 45/566 Routing instructions carried by the data packet, e.g. active networks
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering

Abstract

Packet forwarding systems and methods allow packet-layer transparent, multi-stage packet forwarding among a set of network access points. Packet forwarding across networks utilizing the invention is directly controllable through the upper-layer nodes, e.g. routers, interconnected by such transparent packet forwarding networks. The systems and methods provide packet-layer routing, switching and forwarding look-up-table free and transparent forwarding of label-encapsulated multi-protocol packet traffic among a set of routers. 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. The invention replaces the need for packet forwarding look-up-tables in a router interconnect network by a set of rules using which such network forwards packets directly based on their forwarding labels inserted in the packet headers by the routers exchanging packets through said network, thus simplifying network management and equipment implementation, and facilitating optimization of packet traffic flow across communications networks.

Claims

1. A method for delivering data packets over a network, the method comprising:

receiving a data packet, the data packet including a stack of one or more forwarding instruction tags (FITs) and a set of one or more active tag identifier (ATIs), wherein the set of ATIs activate one of the FITs in the stack to be used at a next stage of forwarding;

determining a next hop destination corresponding to the FIT that is activated by the set of ATIs in the data packet;

modifying the ATIs to indicate a subsequent active FIT, if any, in the stack; and

forwarding the data packet to the determined next hop destination.

2. The method of claim 1, wherein each FIT comprises an ATI.

3. The method of claim 1, wherein each FIT is of constant length in bits.

4. The method of claim 1, wherein the FITs comprise information fields whose contents indicate whether a given set of FITs are concatenated, to form one logical FIT entry.

5. The method of claim 1, wherein at least one of the FITs includes an indication of to which one or ones of a set of next-hop destinations the packet is intended to be forwarded.

6. The method of claim 1, wherein at least one of the FITs includes an individualized indication per at least one next-hop destination of whether the packet is intended to be forwarded to that destination.

7. The method of claim 1, further comprising:

at a final stage of forwarding, reverting the ATIs of the packet to their original values in which they were when the packet was first received by the network.

8. The method of claim 7, wherein at the final forwarding stage, the ATIs are reverted to their original values by marking as active the first FIT and as inactive the other FITs in the stack.

9. A network system for delivering data packets, wherein one or more of the data packets has a header including a stack of one or more forwarding instruction tags (FITs) and a set of one or more active tag identifiers (ATIs), the network system comprising:

a set of network devices,

at least at one of the network devices, an ingress forwarding engine configure to i) forward a packet received over an external interface based at least in part on a FIT marked as active by the set of ATIs in the header of the packet, and ii) modify the ATIs to mark as active a subsequent FIT for a subsequent stage of forwarding in the network system, if any such stage exists.

10. The network system of claim 9, wherein each FIT comprises an ATI.

11. The network system of claim 9, wherein each FIT is of equal length in bits.

12. The network system of claim 9, wherein the FITs comprise information fields whose contents indicate whether a given set of FITs are concatenated, to form one logical FIT entry.

13. The network system of claim 9, wherein at least one of the FITs includes an indication of to which one or ones of a set of next-hop destinations the packet is intended to be forwarded.

14. The network system of claim 9, wherein at least one of the FITs includes an individualized indication per at least one next-hop destination of whether the packet is intended to be forwarded to that destination.

15. The network system of claim 9 further comprising:

at least at one of the network devices, an egress forwarding engine that, if configured as functioning as a final stage of forwarding in the network system, reverts the ATIs of the packet to their original values in which they were when the packet was first received by the network system.

16. The network system of claim 15, wherein the egress forwarding engine reverts the ATIs of the packet to their original values by marking as active the first FIT and as inactivate the other FITs.

17. A network device for forwarding data packets, wherein one or more of the data packets has a header including a stack of one or more forwarding instruction tags (FITs) and a set of one or more active tag identifiers (ATIs), the network device providing:

at least one access interface,

a set of one or more connections, each transporting data packets to its corresponding destination network device,

an ingress forwarding engine configured to i) forward a packet received over an access interface to a destination network device over its corresponding connection, based at least in part on a FIT marked as active by the set of ATIs in the packet header, and ii) unless configured otherwise, modify the ATIs to mark as active a subsequent FIT in the packet header.

18. The network device of claim 17, wherein each FIT comprises an ATI.

19. The network device of claim 17, wherein all the FITs are of equal length in bits.

20. The network device of claim 17, wherein the FITs comprise information fields whose contents indicate whether a given set of FITs are concatenated, to form one logical FIT entry.

21. The network device of claim 17, wherein at least one of the FITs includes an indication of to which one or ones of a set of next-hop destinations the packet is intended to be forwarded.

22. The network device of claim 17, wherein at least one of the FITs includes an individualized indication per at least one next-hop destination of whether the packet is intended to be forwarded to that destination.

23. The network device of claim 17 further comprising:

an egress forwarding engine that, if configured as functioning as a final stage of forwarding in the network system, reverts the ATIs of the packet to their original values in which they were when the packet was first received by the network system.

24. A method for delivering data packets over a network, the method comprising:

sending a data packet to a network comprising a plurality of network devices, the data packet including a stack of one or more forwarding instruction tags (FITs) and a set of one or more active label indicators (ATIs), wherein the set of ATIs activate one of the FITs in the stack to be used at a next stage of forwarding;

at each of a set of the network devices,

receiving the data packet,

determining a next hop destination corresponding to the FIT that is activated by the set of ATIs in the data packet,

modifying the ATIs to activate a subsequent FIT, if any, in the stack, and

forwarding the data packet to the determined next hop destination;

at one of the network devices at a final stage of forwarding the data packet in the network,

reverting the ATIs of the packet to their original values in which they were when the packet was first received by the network.

25. A network device for delivering data packets over a network, the device comprising at least one hardware or software instruction stored on a storage medium for causing the device to perform a method comprising:

receiving a data packet, the data packet including a stack of one or more forwarding instruction tags (FITs) and a set of one or more active label indicators (ATIs), wherein the set of ATIs activate one of the FITs in the stack to be used at a next stage of forwarding;

determining a next hop destination corresponding to the FIT that is activated by the set of ATIs in the data packet;

modifying the ATIs to activate a subsequent FIT, if any, in the stack; and

forwarding the data packet to the determined next hop destination.