Packet-layer transparent packet-switching network

• US 8,619,769 B2
• Filed: 02/20/2009
• Issued: 12/31/2013
• Est. Priority Date: 06/12/2008
• Status: Active Grant

• Current Assignee: Mark Sandtrom
• Original Assignee: OLIO Assets LLC (Intellectual Ventures LLC)
• Inventors: Sandstrom, Mark Henrik
• Primary Examiner(s): RENNER, BRANDON M
• Application Number:
  US12/390,387
• Publication Number:
  US 20090310610A1
• Time in Patent Office: 1,775 Days
• Field of Search: 370389-392, 370/395.1, 370/395.5, 370/395.51
• US Class Current: 370/389
• 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 two or more forwarding instruction tags (FITs) and a set of active tag identifiers (ATIs), wherein the set of ATIs indicate one of the FITs in the stack as an active FIT to be used at a next stage of forwarding;

scanning the stack of FITs until a FIT indicated by the ATIs as the active FIT is found, wherein, if it is determined that the topmost FIT is not the active FIT, said scanning continues through one or more subsequent FITs in the stack;

determining a next hop destination corresponding to the active FIT;

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, with one of the FITs having its ATI set to an active value while the other FITs have their ATIs set to inactive values, and

the FIT with its ATI set to the active value is taken as the active FIT.

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 two or more forwarding instruction tags (FITs) and a set of active tag identifiers (ATIs) that mark one of the FITs as an active FIT, the network system comprising:

a set of network devices,

scanning the stack of FITs until a FIT indicated by the ATIs as the active FIT is found, wherein, if it is determined that the topmost FIT is not the active FIT, said scanning continues through one or more subsequent FITs in the stack;

at least at one of the network devices, hardware logic at a forwarding engine configured to i) forward a packet received over an external interface based at least in part on the active FIT, 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, with one of the FITs having its ATI set to an active value while the other FITs have their ATIs set to inactive values, and

the FIT with its ATI set to the active value is taken as the active FIT.

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 two or more forwarding instruction tags (FITs) and a set of active tag identifiers (ATIs) that mark one of the FITs as an

active FIT, 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, hardware logic at a forwarding engine configured to i) scan the stack of FITs until a FIT indicated by the ATIs as the active FIT is found, so that, if it is determined that the topmost FIT is not the active FIT, such scanning continues through one or more subsequent FITs in the stack, ii) forward a packet received over an access interface to a destination network device over its corresponding connection, based at least in part on the active FIT, and iii) 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, with one of the FITs having its ATI set to an active value while the other FITs have their ATIs set to inactive values, and

the FIT with its ATI set to the active value is taken as the active FIT.

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 two or more forwarding instruction tags (FITs) and a set of active tag indicators (ATIs), wherein the set of ATIs indicate one of the FITs in the stack as an active FIT to be used at a next stage of forwarding;

at each of a set of the network devices, receiving the data packet, scanning the stack of FITs until a FIT indicated by the ATIs as the active FIT is found, wherein, if it is determined that the topmost FIT is not the active FIT, said scanning continues through one or more subsequent FITs in the stack, determining a next hop destination corresponding to the active FIT, 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.

26. The method of claim 24, wherein:

each FIT comprises an ATI, with one of the FITs having its ATI set to an active value while the other FITs have their ATIs set to inactive values, and

the FIT with its ATI set to the active value is taken as the active FIT.

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

receiving a data packet, the data packet including a stack of two or more forwarding instruction tags (FITs) and a set of active tag indicators (ATIs), wherein the set of ATIs indicate one of the FITs in the stack as an active FIT to be used at a next stage of forwarding scanning the stack of FITs until a FIT indicated by the ATIs as the active FIT is found, wherein, if it is determined that the topmost FIT is not the active FIT, said scanning continues through one or more subsequent FITs in the stack;

determining a next hop destination corresponding to the active FIT;

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

forwarding the data packet to the determined next hop destination.

27. The device of claim 25, wherein:

each FIT comprises an ATI, with one of the FITs having its ATI set to an active value while the other FITs have their ATIs set to inactive values, and

the FIT with its ATI set to the active value is taken as the active FIT.