Adaptive source routing and packet processing

• US 20050100035A1
• Filed: 04/01/2004
• Published: 05/12/2005
• Est. Priority Date: 11/11/2003
• Status: Abandoned Application

• Current Assignee: Avici Systems Inc.
• Original Assignee: Avici Systems Inc.
• Inventors: Chiou, Derek, Dennison, Larry R., Dally, William J.
• Application Number:
  US10/815,458
• Publication Number:
  US 20050100035A1
• Time in Patent Office: Days
• US Class Current: 370/412
• CPC Class Codes: H04L 45/06 Deflection routing, e.g. hot-potato routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/522 Dynamic queue service slot or variable bandwidth allocation
• CPC Class Codes: H04L 47/564 Attaching a deadline to packets, e.g. earliest due date first
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/6255 queue load conditions, e.g. longest queue first
• CPC Class Codes: H04L 47/626 channel conditions
• CPC Class Codes: H04L 49/101 using crossbar or matrix
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/552 by ensuring the integrity of packets received through redundant connections

Abstract

Paths for packets traveling through a distributed network fabric are chosen using information local to the source of packets. The system allows resequencing of packets at their destination and detecting out-of-order and missing packets.

Claims

1. A method of delivering a data packet from a source node to a destination node connected by several paths, comprising the steps of:

providing packet queues at the source node, each queue associated with at least one path;

selecting a packet queue based on local information indicative of the state of paths;

moving the packet into the selected packet queue; and

moving the packet from the selected packet queue through one of the at least one path associated with the selected packet queue.

2. The method of claim 1 wherein the selecting of a packet queue depends on whether there is another packet queue containing less data.

3. The method of claim 2 wherein the selecting of a packet queue depends on time stamps attached to packets in the queue.

4. The method of claim 1 wherein the selecting of a packet queue depends on whether the amount of data in the queue is over a limit amount for the queue.

5. The method of claim 4 wherein the selecting of a packet queue depends on time stamps attached to packets in the queue.

6. The method of claim 1 wherein the selecting of a packet queue depends on the priority assigned to the queue and the depths of all the queues.

7. The method of claim 1 wherein the selecting of an emergency packet queue depends on whether the amount of data in non-emergency packet queues is over a limit amount.

8. The method of claim 1 wherein the selecting of a packet queue depends on time stamps attached to packets in the queue.

9. The method of claim 1 further comprising

providing destination packet queues at the destination node;

attaching to each data packet a destination packet queue identifier;

placing the packets into the destination packet queues; and

after extracting a first packet from its destination packet queue, extracting a second packet from the destination packet queue identified by the destination packet queue identifier attached to the first packet.

10. The method of claim 1 further comprising

providing destination packet queues at the destination node;

before a data packet arrives at the destination node, attaching an epoch identifier to the data packet; and

determining that a packet has been lost based on an unexpected change in the epoch identifier.

11. The method of claim 1 wherein data packets are source routed from the source node.

14. The method of claim 11 further comprising

before a data packet arrives at the node, attaching an epoch identifier to the data packet;

and

determining that a packet has been lost based on an unexpected change in the epoch identifier.

12. A method of re-sequencing data packets arriving at a node on a network comprising the steps of:

providing packet queues at the node;

attaching to each data packet a queue identifier;

placing the packets into the queues;

after extracting a first packet from its queue, extracting a second packet from the queue identified by the queue identifier attached to the first packet.

13. The method of claim 12 further comprising associating each output queue with a path through the network to the node from a source node.