Node emulator

• US 7,805,287 B1
• Filed: 06/05/2003
• Issued: 09/28/2010
• Est. Priority Date: 06/05/2003
• Status: Expired due to Fees

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Verizon Laboratories Incorporated (Verizon Communications Inc.)
• Inventors: Jones, Lawrence W.
• Primary Examiner(s): Shah; Kamini S
• Assistant Examiner(s): GEBRESILASSIE, KIBROM K
• Application Number:
  US10/455,567
• Time in Patent Office: 2,672 Days
• Field of Search: 703/26, 703/17, 703/23, 703/6, 703/13, 709/223, 709/238, 709/219, 709/229, 714/776, 714/815, 714/822, 725/97, 725/98, 370/395.53
• US Class Current: 703/13
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/127 by using congestion prediction
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames

Abstract

System, methods and apparatii are provided for emulating the performance effect on network traffic flow traversing a node in a communications network. According to one illustrative embodiment, a method of emulating the performance effect on network traffic through a node is provided that includes generating foreground traffic through the node; simulating background traffic at the node; determining an effect of the background traffic on the foreground traffic; and making a forwarding decision with respect to the foreground traffic based on the effect.

Claims

1. A method of emulating network traffic through a node having connections to a server and a client, comprising:

(a) generating foreground traffic through the node from the server to the client, wherein the foreground traffic comprises foreground data packets;

(b) simulating background traffic internally at the node, the simulated background traffic contending with the foreground traffic at the node;

(c) determining, at the node, an effect of the simulated background traffic on the foreground traffic received at the node, wherein the determining comprises simulating a queue based on at least the simulated background traffic and the foreground traffic received at the node, wherein the determining further comprises;

computing a rate of growth of the simulated queue based on at least the simulated background traffic and an output link capacity associated with the node; and

calculating a length of the simulated queue based on at least the computed rate of growth and lengths of the foreground data packets; and

(d) making a forwarding decision at the node with respect to the foreground traffic based on the calculated length of the simulated queue, wherein the forwarding decision comprises one of;

(i) forwarding at least one of the foreground data packets through the node via an egress media interface to the connection to the client;

or discarding at least one of the foreground data packets.

2. The method of claim 1, wherein the computing comprises computing the rate of growth of the simulated queue according to:

a[k]=R[k]−

(1/8)*C,

wherein;

a[k] represents the rate of growth of the simulated queue (in bytes per second) for a duration of a kth timeslot;

R[k] represents a background traffic volume (in bytes per second) generated during the kth time slot; and

C represents the output link capacity of the node (in bits per second).

3. The method of claim 1, wherein the forwarding decision comprises one of:

scheduling the foreground data packet to be forwarded through the node, forwarding the foreground data packet through the node, and discarding the foreground data packet.

4. The method of claim 1, wherein the forwarding decision includes delaying forwarding the foreground data packet for a period of time.

5. The method of claim 4, wherein the forwarding decision includes calculating the period of time.

6. The method of claim 5, wherein the period of time simulates the length of time the foreground data packet remains in the simulated queue before being forwarded from the node.

7. The method of claim 1, wherein the forwarding decision includes discarding the foreground data packet when it is determined that the simulated background traffic and foreground traffic would cause the simulated queue to overflow.

8. The method of claim 1, wherein step (b) includes simulating a rate of background traffic.

9. The method of claim 8, wherein simulating the rate of background traffic comprises simulating the background traffic at a rate of a number of bytes per second.

10. The method of claim 9, wherein the number of bytes per second is randomly selected.

11. The method of claim 10, wherein the simulated rate is assigned via a lookup table.

12. The method of claim 1, wherein the foreground traffic has a first priority and wherein step (b) includes assigning the simulated background traffic a second priority that is different from the first priority.

13. The method of claim 1, wherein the length of the simulated queue includes at least the length of an incoming foreground data packet plus the length of the simulated queue just prior to the receipt of the incoming foreground data packet.

14. A node emulator, having connections to a server and a client, comprising:

an ingress media interface, which receives incoming foreground traffic from the connection to the server;

a packet queue to receive incoming foreground traffic from the ingress media interface, wherein the foreground traffic comprises foreground data packets;

an egress media interface, which transmits foreground traffic to the connection to the client;

a background traffic generator to simulate background traffic internally at the node emulator, the simulated background traffic contending with the foreground traffic at the node emulator; and

a foreground packet scheduler forwarder to cause the foreground data packets to be forwarded from the packet queue to the egress media interface,

wherein the foreground packet scheduler forwarder;

simulates the packet queue based on at least the simulated background traffic and the foreground traffic;

computes a rate of growth of the simulated packet queue based on at least the simulated background traffic and an output link capacity associated with the node emulator;

calculates a length of the simulated packet queue based on at least the computed rate of growth and lengths of the foreground data packets; and

makes a forwarding decision with respect to foreground traffic in the packet queue, the forwarding decision being dependent on the calculated length of the simulated packet queue, and wherein the forwarding decision comprises one of;

(i) forwarding a foreground data packet through the node emulator to the egress media interface;

or (ii) discarding the foreground data packet.

15. The node emulator of claim 14, wherein the foreground packet scheduler forwarder computes the rate of growth of the simulated queue according to:

a[k]=R[k] −

(1/8)*C,

wherein;

a[k] represents the rate of growth of the simulated queue (in bytes per second) for the duration of a kth timeslot;

R[k] represents a background traffic volume (in bytes per second) generated during the kth time slot; and

C represents the output link capacity of the node (in bits per second).

16. The node emulator of claim 14, wherein the forwarding decision includes delaying forwarding the data packet for a period of time.

17. The node emulator of claim 16, wherein the forwarding decision includes calculating the period of time.

18. The node emulator of claim 17, wherein the period of time simulates the length of time the data packet remains in the simulated queue before being forwarded from the node.

19. The node emulator of claim 14, wherein the forwarding decision includes discarding the foreground data packet when it is determined that the simulated background traffic and foreground traffic would cause the simulated queue to overflow.

20. The node emulator of claim 14, wherein the foreground packet scheduler forwarder is a software application running on the node emulator.

21. The node emulator of claim 14, wherein the forwarding decision comprises one of:

forwarding the foreground data packet through the node to the egress media interface, discarding the foreground data packet, and scheduling the foreground data packet for forwarding to the egress media interface.

22. The node emulator of claim 14, wherein the scheduling is dependent at least in part on an amount of the simulated background traffic.

23. A system to emulate the effect of simulated background traffic on foreground traffic comprising:

a server to generate foreground traffic, wherein the foreground traffic includes foreground data packets;

a node emulator coupled to the server and configured to receive the foreground traffic, to simulate background traffic to contend with the foreground traffic at the node, and to forward the foreground traffic via an egress media interface; and

a client coupled to the node emulator to receive the foreground traffic forwarded from the node emulator via the egress media interface,

wherein the node emulator;

simulates a queue based on at least the simulated background traffic and the foreground traffic received at the node emulator;

computes a rate of growth of the simulated queue based on at least the simulated background traffic and an output link capacity associated with the node emulator;

calculates a length of the simulated queue based on at least the computed rate of growth and lengths of the foreground data packets; and

makes a forwarding decision with respect to the foreground traffic dependent on the computed length of the simulated queue, and wherein the forwarding decision includes one of;

(i) discarding a foreground data packet;

or (ii) scheduling the foreground data packet for forwarding to the client.

24. The system of claim 23, wherein the node emulator computes the rate of growth of the simulated queue according to:

a[k]=R[k] −

(1/8)*C,

wherein;

a[k] represents the rate of growth of the simulated queue (in bytes per second) for the duration of a kth timeslot;

R[k] represents a background traffic volume (in bytes per second) generated during the kth time slot; and

C represents the output link capacity of the node (in bits per second).

25. The system of claim 23, wherein the forwarding decision includes one of:

discarding a foreground data packet, forwarding the foreground data packet to the client, or scheduling the foreground data packet for forwarding to the client.

26. A computer readable medium containing instructions for performing a method of emulating network traffic through a node having connections to a server and a client, the method comprising:

(a) simulating background traffic internally at the node, the simulated background traffic contending with foreground traffic received at the node;

(b) determining, at the node, an effect of the simulated background traffic on the foreground traffic received at the node, wherein the foreground traffic comprises foreground data packets received at the node, wherein the determining comprises simulating a queue based on at least the simulated background traffic and the foreground traffic received at the node, wherein the determining further comprises;

computing a rate of growth of the simulated queue based on at least the simulated background traffic and an output link capacity associated with the node; and

calculating a length of the simulated queue based on at least the computed rate of growth and lengths of the foreground data packets; and

(c) making a forwarding decision, at the node, with respect to the foreground traffic, depending on the calculated length of the simulated queue, and wherein the forwarding decision includes one of;

(i) discarding a foreground data packet;

or scheduling the foreground data packet for forwarding to the connection to the client via an egress media interface.

27. The computer readable medium of claim 26, wherein the computing comprises computing the rate of growth of the simulated queue according to:

a[k]=R[k] −

(1/8)*C,

wherein;

a[k] represents the rate of growth of the simulated queue (in bytes per second) for the duration of a kth timeslot;

R[k] represents a background traffic volume (in bytes per second) generated during the kth time slot; and

C represents the output link capacity of the node (in bits per second).

28. The computer readable medium of claim 26, wherein the forwarding decision includes one of:

discarding the foreground data packet, forwarding the foreground data packet to the server, or scheduling the foreground data packet for forwarding to the server.