Method and system for operating an edge router

• US 20030007485A1
• Filed: 05/22/2001
• Published: 01/09/2003
• Est. Priority Date: 05/22/2001
• Status: Abandoned Application

• Current Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Emeott, Stephen P., Venkitaraman, Narayanan, Mysore, Jayanth Pranesh
• Application Number:
  US09/862,379
• Publication Number:
  US 20030007485A1
• Time in Patent Office: Days
• 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/302 Route determination based on requested QoS
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames

Abstract

A method for operating an edge router in a network that provides multiple levels of service is provided. In response to receiving packets, the edge router determines a corresponding packet flow. An incremental utility for each packet is then calculated, and each packet is labeled as a function of the incremental utility. The packets are then forwarded to core routers in the network, where they are processed based on the labels. The incremental utility can be based on a utility function corresponding to the flow and intra-flow priorities associated with the packets.

Claims

1. A method of operating an edge router, comprising:

receiving a plurality of packets;

determining a flow corresponding to the plurality of packets;

determining an incremental utility for each of the packets;

labeling each of the packets with a label as a function of the incremental utility; and

processing each of the packets based on the label.

2. The method of claim 1, wherein the step of determining the incremental utility includes:

obtaining a utility function corresponding to the flow;

determining an intra-flow priority corresponding to each of the packets; and

determining the incremental utility based on the utility function and the intra-flow priority.

3. The method of claim 2, further comprising:

obtaining the utility function from a device selected from the group consisting of a network server and an end host.

4. The method of claim 2, wherein the utility function is stored in the edge router.

5. The method of claim 2, further comprising:

calculating the utility function based on a rule corresponding to one or more incremental utilities that are sequential integers.

6. The method of claim 2, wherein the intra-flow priority is based on packet labeling.

7. The method of claim 6, wherein the packet labeling corresponds to one or more layers of encoding.

8. The method of claim 7, wherein the encoding is selected from the group consisting of MPEG encoding and RLM encoding.

9. The method of claim 2, wherein the intra-flow priority is based on the content of a packet.

10. The method of claim 9, wherein the content is selected from the group consisting of a TCP retry state, a control packet, and a data packet.

11. The method of claim 2, wherein the intra-flow priority is based on the reliability of the packet.

12. The method of claim 2, wherein the intra-flow priority is based on the sensitivity of the order of dropping packets in the flow.

13. The method of claim 2, further comprising:

partitioning the utility function into a plurality of rate intervals.

14. The method of claim 13, wherein each of the rate intervals represents a region of constant incremental utility.

15. The method of claim 1, further comprising:

partitioning the flow into a plurality of rate intervals; and

determining the incremental utility based on the rate intervals.

16. The method of claim 15, wherein the step of partitioning includes:

estimating the rate of the flow; and

determining the number of packets per second that belong to each of the rate intervals based on at least one estimated rate and at least one packet size.

17. The method of claim 15, wherein the step of partitioning includes:

estimating the rate of the flow; and

determining the number of packets per second that belong to each of the rate intervals based on an epoch length and a packet size.

18. The method of claim 15, further comprising:

calculating the incremental utility corresponding to each of the rate intervals assigned to a packet and based on a utility function.

19. The method of claim 1, wherein the label is proportional to the incremental utility.

20. The method of claim 1, wherein the label is proportional to the incremental utility combined with a stability factor.

21. A network router, comprising:

means for receiving a plurality of packets;

means for determining a flow corresponding to the plurality of packets;

means for determining an incremental utility for each of the packets;

means for labeling each of the packets with a label as a function of the incremental utility; and

means for processing each of the packets based on the label.

22. The router of claim 21, wherein the means for determining the incremental utility includes:

means for obtaining a utility function corresponding to the flow;

means for determining an intra-flow priority corresponding to each of the packets; and

means for determining the incremental utility based on the utility function and the intra-flow priority.

23. The router of claim 22, further comprising:

means for partitioning the utility function into a plurality of rate intervals.

24. The router of claim 22, further comprising:

means for partitioning the utility function into a plurality of rate intervals.

25. The router of claim 21, further comprising:

means for partitioning the flow into a plurality of rate intervals; and

means for determining the incremental utility based on the rate intervals.

27. The computer-usable medium of claim 26, wherein the step of determining the incremental utility includes:

obtaining a utility function corresponding to the flow;

determining an intra-flow priority corresponding to each of the packets; and

determining the incremental utility based on the utility function and the intra-flow priority.

28. The computer-usable medium of claim 27, further comprising:

partitioning the utility function into a plurality of rate intervals.

29. The computer-usable medium of claim 26, further comprising:

partitioning the flow into a plurality of rate intervals; and

determining the incremental utility based on the rate intervals.

26. A computer-usable medium storing a computer program for directing a network router to perform the steps of:

receiving a plurality of packets;

determining a flow corresponding to the plurality of packets;

determining an incremental utility for each of the packets; and

labeling each of the packets with a label as a function of the incremental utility.