Method and apparatus for packet scheduling using virtual time stamp for high capacity combined input and output queued switching system

• US 20020129158A1
• Filed: 12/03/2001
• Published: 09/12/2002
• Est. Priority Date: 12/01/2000
• Status: Active Grant

• Current Assignee: Cisco Linksys LLC (Cisco Systems, Inc.)
• Original Assignee: Cisco Linksys LLC (Cisco Systems, Inc.)
• Inventors: Zhang, Zhi-Li, Hou, Yiwei Thomas
• Granted Patent: US 7,277,962 B2
• Time in Patent Office: Days
• US Class Current: 709/234
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/28 in relation to timing considerations
• CPC Class Codes: H04L 47/31 by tagging of packets, e.g. using discard eligibility [DE] bits

Abstract

A method and apparatus for packet scheduling using a virtual time stamp for a high capacity combined input and output queued switching system. A network employs a virtual time reference system (VTRS) to generate packet virtual time stamps associated with each packet traversing the network. The VTRS includes edge conditioners located at the edge of the network that receive unregulated packet traffic and generate regulated packet traffic for a given flow. The edge conditioners also add a packet virtual time stamp to each incoming packet. Core routers within a network core reference the packet virtual time stamps to schedule packet flow. The core routers also update the packet virtual time stamps using virtual delays. The packet virtual time stamps are removed from the packets when the packets leave the network core through an edge conditioner.

Claims

1. A method for scheduling packets in a network, the method comprising:

generating a packet state including a virtual time stamp for each of the packets;

associating the packet states with the packets; and

matching packets to switch outputs using the packet states.

2. The method of claim 1 further comprising generating regulated packet traffic for a flow using the packets.

3. The method of claim 2, wherein generating regulated packet traffic further includes using a size of each packet and a reserved flow rate.

4. The method of claim 1, the method further comprising initializing the packet virtual time stamp for each packet using the actual arrival time of each packet at a switch.

5. The method of claim 1, the method further comprising updating the packet virtual time stamp for each packet using each packet'"'"'s packet virtual time stamp and a virtual delay.

6. The method of claim 5 wherein updating the packet virtual time stamp further includes using an error term.

7. The method of claim 5 wherein updating the packet virtual time stamp further includes using a propagation delay.

8. The method of claim 5 wherein the virtual delay is generated using a delay parameter.

9. The method of claim 8 wherein the packet state further includes the delay parameter.

10. The method of claim 5, wherein the virtual delay is generated using the size of each packet, a flow rate reserved for a flow including each packet, and a virtual time adjustment term.

11. The method of claim 10, wherein the packet state further includes the reserved flow rate and the virtual time adjustment term.

12. The method of claim 1, wherein matching packets to switch outputs further includes:

generating a virtual finish time for each packet; and

matching packets to switch outputs using the virtual finish times.

13. The method of claim 12, wherein matching packets to switch outputs using the virtual finish times further includes matching packets with the smallest virtual finish times to switch outputs.

15. The network of claim 14, wherein the edge conditioner generates regulated packet traffic for a flow using a size of each of the packets and a reserved flow rate.

16. The network of claim 14, wherein the switch initializes the packet virtual time stamp for each packet using the actual arrival time of each packet at the router.

17. The network of claim 14, wherein the switch updates the packet virtual time stamp for each packet using each packet'"'"'s packet virtual time stamp and a virtual delay.

18. The method of claim 17 wherein updating the packet virtual time stamp further includes using an error term.

19. The method of claim 17 wherein updating the packet virtual time stamp further includes using a propagation delay.

20. The network of claim 17 wherein the virtual delay is generated using a delay parameter.

21. The network of claim 20 wherein the packet state further includes the delay parameter.

22. The network of claim 17, wherein the virtual delay is generated using the size of each packet, a flow rate reserved for a flow including each packet, and a virtual time adjustment term.

23. The network of claim 22, wherein the packet state further includes the reserved flow rate and the virtual time adjustment term.

24. The network of claim 14, wherein the switch matches packets to switch outputs by determining a virtual finish time for each packet.

25. The network of claim 24, wherein the switch matches packets to switch outputs using the smallest virtual finish times

27. The method of claim 26, the method further comprising initializing the packet virtual time stamp for each packet using the actual arrival time of each packet at a switch.

28. The method of claim 26, the method further comprising updating the packet virtual time stamp for each packet using each packet'"'"'s packet virtual time stamp and a delay parameter included in the packet state.

29. The method of claim 26, the method further comprising updating the packet virtual time stamp for each packet using each packet'"'"'s packet virtual time stamp, the size of each packet, and a flow rate reserved for a flow including each packet, and a virtual time adjustment term included in the packet state.

14. A network comprising:

an edge conditioner generating a packet state associated with each packet traversing the network, the packet state including a virtual time stamp; and

a switch operably coupled to the edge conditioner, the switch matching packets to switch outputs using the virtual time stamps included in the packet states.

26. A method for scheduling packets in a network, the method comprising:

generating regulated packet traffic for a flow from the packets using a size of each of the packets and a reserved flow rate;

generating a packet state including a virtual time stamp for each of the packets;

associating the packet states with the packets;

generating a virtual finish time for each packet using the virtual time stamp and a virtual delay ; and

matching packets with the smallest virtual finish times to switch outputs.

30. An apparatus for scheduling packets in a network, the apparatus comprising:

means for generating a packet state including a virtual time stamp for each of the packets;

means for associating the packet states with the packets; and

means for matching packets to switch outputs using the packet states.

31. The apparatus of claim 30 further comprising means for generating regulated packet traffic for a flow using the packets.

32. The apparatus of claim 31, wherein the means for generating regulated packet traffic uses a size of each packet and a reserved flow rate to generate the regulated packet traffic.

33. The apparatus of claim 30, the apparatus further comprising means for initializing the packet virtual time stamp for each packet using the actual arrival time of each packet at a switch.

34. The apparatus of claim 30, the apparatus further comprising means for updating the packet virtual time stamp for each packet using each packet'"'"'s packet virtual time stamp and a virtual delay.

35. The apparatus of claim 34 wherein the means for updating the packet virtual time stamp further uses an error term to update the packet virtual time stamp.

36. The apparatus of claim 34 wherein the means for updating the packet virtual time stamp uses a propagation delay to update the packet virtual time stamp.

37. The apparatus of claim 34 further comprising means for generating the virtual delay using a delay parameter.

38. The apparatus of claim 37 wherein the packet state further includes the delay parameter.

39. The apparatus of claim 34, further comprising means for generating the virtual delay using the size of each packet, a flow rate reserved for a flow including each packet, and a virtual time adjustment term.

40. The apparatus of claim 39, wherein the packet state further includes the reserved flow rate and the virtual time adjustment term.

41. The apparatus of claim 30, wherein the means for matching packets to switch outputs further includes:

means for generating a virtual finish time for each packet; and

means for matching packets to switch outputs using the virtual finish times.

42. The apparatus of claim 41, wherein the means for matching packets to switch outputs using the virtual finish times further includes means for matching packets with the smallest virtual finish times to switch outputs.