Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1999-03-26
2003-02-04
Yao, Kwang Bin (Department: 2662)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S468000, C370S395410
Reexamination Certificate
active
06515965
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to routing of packets in a telecommunications network, and, more particularly, to allocating bandwidth capacity between nodes of a packet network using flow control for routing of packets.
2. Description of the Related Art
Service providers provision and maintain packet networks for clients having a variety of voice and data needs. For example, virtual private networks (VPNs) allow service providers to establish and tear down connections for a large number of users while only billing a single client. Each of these connections, which may be termed a session, may comprise a stream of packets, or packet flow, traversing links of the network. However, the client may require a certain amount of guaranteed bandwidth, minimum transport delay, or other metric for some or all of the packet flows transported through the network for a session. Routing methods may determine paths through links of the network and allocate portions of the corresponding bandwidth of the links to the sessions.
Network operators may commit to certain levels of service for sessions, such as guaranteed minimum available bandwidth or maximum packet-loss probability. Some networks, particularly high-speed networks, may support the networking protocol known as asynchronous transfer mode (ATM) in which data are transmitted as packets (termed “cells”) through a logical path. Such high-speed networks typically carry multiple services having different traffic characteristics, including both constant bit rate traffic and variable bit rate traffic. One type of service provided in ATM networks is the available bit rate (ABR) service. Bandwidth commitments for the ABR service may include: 1) a minimum cell rate (MCR) available to a service (i.e., the least bandwidth that the network may allocate to a service), and 2) a peak cell rate (PCR) that the service may transmit cells (i.e., the maximum bandwidth that the network may allocate to a service). However, the network may require a mechanism for allocating bandwidth to the sessions sharing the total capacity of a link.
Packet networks of the prior art have employed a classic max-min (rate-allocation) policy as a mechanism for sharing bandwidth of the network for the ABR service. A max-min policy maximizes the minimum available bandwidth (i.e., cell rate) assigned to a session.
FIG. 1
illustrates a network with sources S
1
104
and S
2
105
each establishing a point-to-point connection (session) with corresponding destinations D
1
106
and D
2
107
. The bandwidth capacity for the connections passing through a link
103
between switches (SWs)
101
and
102
is shared. For the classic max-min policy, users that correspond to the source-destination pairs (S
1
104
and D
1
106
) and (S
2
105
and D
2
107
) each receives the same service level commitments from the service provider.
Each of the sources S
1
104
and S
2
105
initiating a session sends a request to the corresponding destination D
1
106
or D
2
107
to reserve bandwidth of the link
103
through which the connection passes. In ATM networks, this request is referred to as a resource management (RM) cell. The forward RM cell (from source to destination) contains the MCR and PCR values and an explicit cell rate (ER) set to the PCR value. A backward RM cell (from destination to source) contains the ER set to the assigned cell rate (i.e., allocated bandwidth). Typically, the bandwidth allocated to a connection by SWs
101
and
102
for each source-destination pair is the available bandwidth (remaining capacity) of link
103
divided by the number of connections. This classic max-min policy works well for a network when each session's MCR is zero and each session's PCR is greater than or equal to the link rate. However, for the general case of multiple users having different commitments for MCR/PCR, the classic max-min policy no longer determines rate allocation sufficiently since the classic max-min policy does not account for either the MCR or PCR of a user's connection.
Other networks of the prior art providing ABR services may employ distributed algorithms to provide a max-min rate allocation for a sharing mechanism. In particular, the Consistent Marking method (outlined subsequently) for a distributed algorithm converges to the classical max-min policy through distributed and asynchronous iterations. The Consistent Marking method is described in, for example, A. Charny, D. Clark, and R. Jain, “Congestion Control with Explicit Rate Indication,”
Proc. IEEE ICC'
95 (1995) pp. 1954-1963.
According to the Consistent Marking method, each switch (e.g., SW
101
and
102
of
FIG. 1
) monitors the cell traffic traversing through the switch by keeping track of the state information of each session. Also, each output port of switches
101
and
102
maintains a variable, the advertised rate &mgr;, to calculate available bandwidth (capacity) for each connection. An algorithm employing Consistent Marking method operates as follows.
When a forward RM cell arrives at SW
101
, for example, the current cell rate (CCR) value of the session is stored in a virtual circuit (VC) table. If this CCR value is less than or equal to the current advertised rate &mgr;, then the session is assumed to be in a bottlenecked state (i.e., the session cannot increase its cell rate because link capacity is unavailable), either at the link of the switch or at a link elsewhere within the network. Initially, the current advertised rate is set to the capacity of the link divided by the number of sessions traversing the link. A bit associated with this session is set (marked) within the VC table (the session having the corresponding VC table bit set is termed a “marked session”). The advertised rate &mgr; for the link is then calculated as given by equation (1):
Advertised
Rate
μ
=
C
l
-
∑
Rates
of
marked
connections
n
l
-
∑
Marked
connections
(
1
)
where C
l
is the capacity of link l and n
l
is the number of connections of link l. The switch sets the ER field of the forward RM cell of the marked session to the calculated advertised rate &mgr;. The advertised rate &mgr; is continuously re-calculated as sessions are initiated, terminated, or updated.
For each re-calculation, the algorithm using the Consistent Marking method examines the entries of sessions in the VC table. For each marked session, if the recorded CCR of the marked session in the VC table is larger than the newly calculated advertised rate &mgr;, the associated bit for the session is reset (the session is “unmarked”) and the advertised rate &mgr; is calculated again. Consequently, the ER field of the forward RM cell is set by the switches to the minimum of all advertised rates along the links traversed by the connection. The destination then returns a backward RM cell to the source with this ER value. Upon convergence of the Consistent Marking method, each session is allocated with a rate according to the max-min policy, and is marked along every link the session traverses. However, this method does not effectively account for the MCR and PCR of each session.
SUMMARY OF THE INVENTION
The present invention relates to allocating capacity of one or more links of a network by a router to a packet flow of at least one session, each session having a minimum rate and a peak rate. In accordance with the present invention, each session is initially assigned a rate based on the minimum rate of the session. A session is selected based on the initially assigned rate. An iterative procedure then increases the rate of the session if an available capacity of the link exists, and then determines whether the rate of the session that has been increased is equal to the corresponding peak rate of the session or the available capacity of the link. If the session that has been increased is equal to the corresponding peak rate of the session, then the rate
Hou Yiwei T.
Panwar Shivendra S.
Tzeng Hong-Yi
Lucent Technologies - Inc.
Mendelsohn and Associates PC
Nguyen Hanh
Yao Kwang Bin
LandOfFree
Available bit rate flow control for service allocation in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Available bit rate flow control for service allocation in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Available bit rate flow control for service allocation in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3118122