Random early demotion and promotion marker

Details Random early demotion and promotion marker Random early demotion and promotion marker

2000-04-28

2004-06-08

Wiley, David (Department: 2143)

Electrical computers and digital processing systems: multicomput

Computer network managing

Computer network access regulating

C709S229000, C709S240000, C370S235100, C370S230000, C370S232000

Reexamination Certificate

active

06748435

ABSTRACT:

BACKGROUND AND SUMMARY OF THE INVENTION
The present invention relates generally to network systems. More particularly, the invention relates to a traffic conditioning marker associated with a router.
With the explosive growth of the internet, there is a growing interest in using the internet and other internet protocol-based networks to deliver high bandwidth selections such as multi-media video and audio material. The internet is a connectionless network offering best effort delivery service. Packets of data are routed to an address of an intended recipient whose address is contained in the packet. A specific connection between the sender and the intended recipient is not required because all host nodes on the network include the inherent capability to route packets from node to node until delivery occurs.
The packet delivery scheme is constructed as a best effort delivery system in which the delivery of packets is not guaranteed. Packets may be sent via different routes in an effort to increase the likelihood of delivery. Thus, if one node on the network is experiencing congestion, subsequent packets may be alternatively routed to avoid the congested node. This means that packets do not inherently have a guaranteed arrival time. In other words, packets corresponding to a single message may be received out of order.
Multi-media data often requires real-time delivery. In the case of audio or video data, the data stream representing a particular media selection needs to be delivered in the proper time sequence to allow the user to play back the audio or video selection “live” as it is being sent.
In the best effort service model, the network allocates the bandwidth among all of the contending users as best as it can. The network attempts to serve all of the users without making any commitment to data delivery rates or any other service quality. As multi-media and real-time applications proliferate, it is becoming more desirable to provide service guarantees for internet delivery. Many enterprises and users are willing to pay an additional price to get preferred service from the internet provider.
The integrated services model and the differentiated services model have been proposed to provide guaranteed service. The integrated services model is analogous to the circuit-switched service in the current telephone system. While the integrated services model provides guaranteed service, it has two major drawbacks. First, the amount of state information increases proportionately with the increased flow of data which leads to poor scalability at the core routers. Second, implementation of the integrated services model requires significant changes to the internet infrastructure and, therefore, requires significant expenditures of capital. For these reasons, the integrated services model is not an economically or logistically feasible approach at this time.
The differentiated services model provides a simple and predefined per-hop behavior (PHB) level service differentiation in the internet core routers. Per-flow or flow aggregate marking, shaping and policing are performed at the edge routers. The differentiated services model does not suffer from the scalability problems associated with the integrated services model. The differentiated services model also requires far less significant changes to the existing internet infrastructure.
Referring to
FIG. 1
, a prior art networking system
10
employing the differentiated services model is illustrated and includes a first domain
12
and a second domain
14
. The first and second domains
12
and
14
each include multiple core routers
16
,
18
,
20
,
22
,
24
and
26
that are connected by backbone networks
30
and
32
. The first domain
12
and the second domain
14
are interconnected to each other through edge routers
36
and
38
. End users
40
,
42
,
44
,
46
,
48
, and
50
are likewise connected through edge routers
52
,
54
,
56
, and
58
by stub domain
60
and
62
.
Before entering a differentiated services domain, such as the first domain
12
, a packet is assigned a differentiated services code point (DSCP) by a traffic conditioning marker associated with edge router
52
. When the packet reaches a differentiated services aware router such as the core router
18
, the DSCP contained in the packet is checked to determine a forwarding priority of the packet.
The DSCP contained in the packet may be changed when it crosses a boundary of two domains. For example, in
FIG. 1
a packet is sent by one of the end users
40
,
42
,
44
associated with host
60
to one of the end users
46
,
48
, or
50
associated with stub domain
62
. The packet may be marked by the edge router
52
or by another marker associated with the stub domain
60
as a high priority DSCP packet when the packet enters the first domain
12
.
At a boundary
64
between the first domain
12
and the second domain
14
, the marker at the edge router
38
may remark the packet as a low priority DSCP packet before forwarding the packet to the second domain
14
if the first domain
12
has not negotiated enough traffic forwarding rate with the second domain
14
for the requested priority level.
Currently, a single class for expedited forwarding (EF) and four classes for assured forwarding (AF) have been defined. EF was originally proposed to be used for premium services. After EF and AF were defined, it was expected that premium services traffic would be allocated only a small percentage of network capacity and would be assigned to a high-priority queue in the routers. EF is ideal for real-time services such as internet protocol (IP) telephony, video conferences, and other real time multi-media applications.
AF is used for assured services. The Red-In/Out (RIO) approach was proposed to ensure that the expected capacity specified by a traffic profile is obtained. Upon the arrival of each packet, the packet is marked as “In” or “Out” depending upon whether the packet is within the traffic profile. When a differentiated services-aware router is employed, all of the incoming packets are queued in the original transmission order. During network congestion, however, the router drops the packets that are marked as “Out”. If the network controls the aggregate “In” packets such that they do not exceed the capacity of the link, the throughput of each flow or flow aggregate can be assured to be at least the rate defined in the traffic profile.
To ensure service differentiation, Assured Forwarding Per-Hop Behavior (AFPHB) specifies four traffic classes with three drop precedence levels within each class. In all, there are 12 DSCP's for AFPHB. Within an AF class, a packet is marked as one of three colors, green, yellow or red. Green has the lowest drop probability and red has the highest drop probability.
An internet connection typically spans a path involving one or more network domains as is illustrated in FIG.
1
. If a guaranteed arrival is desired, the network system
10
must ensure that the aggregate traffic along the path does not exceed any of the inter-domain negotiated traffic rates. This is very difficult since the inter-domain service agreements are not usually renegotiated at the initiation of each new connection. For AF, the inter-domain traffic rates are usually negotiated statically and/or updated periodically to avoid signaling overhead and scalability problems. The negotiation is usually based on statistical estimation. At any given time, the aggregate flow rate may be higher or lower than the negotiated rate.
Referring now to
FIG. 2
, a traffic conditioning marker
68
that is typically located in an edge router between an upstream domain
70
and a downstream domain
72
is illustrated and includes a packet classifier
76
which separates “In” packets from “Out” packets. A rate generator
78
defines a negotiated token rate of r bits per second. A packet remarker
80
determines whether to remark some of the “In” packets as “Out” packets depending upon a maximum burst rate b, the incoming flow rate of “In” packets, and the negotiated

Affiliated with

Also associated with

Rating

Random early demotion and promotion marker does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Random early demotion and promotion marker, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random early demotion and promotion marker will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3363325