Multiplex communications – Channel assignment techniques – Adaptive selection of channel assignment technique
Reexamination Certificate
2000-01-12
2004-05-11
Sam, Phirin (Department: 2661)
Multiplex communications
Channel assignment techniques
Adaptive selection of channel assignment technique
C370S411000, C370S412000, C370S468000
Reexamination Certificate
active
06735214
ABSTRACT:
FIELD OF INVENTION
The present invention relates to the field of packet based communication systems and particularly switching technology.
BACKGROUND
Telephony, desktop video conferencing, video on demand, and other popular networking applications impose an increasing demand for bandwidth and simultaneous support of different types of service on the same communication network. To meet these demands, various high performance communication technologies are being deployed, including transmission over cable television lines using cable modems and DSL telephony services. One prominent data packet based technology is Asynchronous Transfer Mode (ATM).
ATM is designed to deal with the problem that some applications require very low latency, while other applications cannot tolerate loss of information but can support reasonable delays. Users also want a predictable and consistent level of quality when using a service. Quality of service (QoS) therefore becomes a key factor in the deployment of the next generation of networks. QoS differentiates services from one another by category. A service is represented to be a certain quality if it can consistently meet the same level of quality for a given set of measurable parameters. In traditional telephone systems, for example, QoS is measured in terms of delay to obtain dial tone, delay to set up the connection, trunk availability, quality of sound (e.g., noise, echo), and reliability of the connection. On the other hand, the Internet was designed as a “best effort” network, and did not originally intend to make any QoS commitments.
The various service categories supported by ATM are constant bit rate (CBR) service, variable bit rate (VBR) service, available bit rate (ABR) services guaranteed frame rate (GFR) service, and the residual category, unspecified bit rate (UBR) service.
In supporting these various service categories, network providers are therefore faced with a set of conflicting requirements. In response to market demand, network providers have to maximize network efficiency while meeting the specific QoS needs of the applications. The networks must also be capable of sharing bandwidth fairly among users and ensuring that any given user traffic cannot affect the QoS of other users. In addition, the networks have to support permanent connections as well as switched connections, which have very different holding time and utilization characteristics. Permanent connection are not set up and torn down frequently, but the link bandwidth may not be utilized at all times. In contrast, switched connections are set up and torn down frequently and the link bandwidth is generally highly utilized during the lifetime of the connection. Because of the diversity in the link speeds both in the accrues to the network and in the trunks, large speed mismatches need to be handled efficiently.
The inherent conflict created by the need to optimize bandwidth while ensuring different QoS can be resolved by using a combination of traffic control or traffic management techniques. A multiservice ATM network provides support for a wide variety of services with differing QoS requirements to be carried on the same switching nodes and links. Multiple services share the network resources (e.g., link bandwidth, buffer space, etc.) and may try to access a resource simultaneously. Resource contention arises because of this sharing, and buffering is required to temporarily store data packets. (In discussions of ATM technology a data packet is customarily referred to as a cell. According, this terminology will be adopted for purposes of this specification.)
The point at which this resource contention occurs is generally referred to as a “queuing” or “contention point”. Depending on the architecture, a switching node can be implemented with one or more queuing structures. A scheduling mechanism is implemented at each queuing structure to appropriately select the order in which cells should be served to meet the QoS objectives. A queuing structure and the corresponding scheduling algorithm attempt to achieve sometimes conflicting goals: (a) the flexibility to support a variety of service categories, and to easily evolve in support of new services; (b) the scalability to be simple enough to allow scaling up to large number of connections while allowing cost effective implementation; (c) the efficiency to maximize the network link utilization; (d) the guaranty of QoS to provide low jitter and end to end delay bounds for real time traffic; and (e) fairness to allow fast and fair redistribution of bandwidth that becomes dynamically available.
A variety of architectures are used to achieve the appropriate degree of traffic shaping. The architecture most pertinent to the present invention is known as direct exact sorting.
FIG. 1
illustrates the direct exact sorting architecture used in the prior art. The direct exact sorting architecture employs a plurality of data structures known as queues. Each queue is a data structure in a which a plurality of cells are stored in memory in a sequential order. (The order is not physically sequential but is ordered by the software of the circuitry of the switch.) Because of the sequential order, there is a first cell and last cell in each queue. The queues release cells on a first-in first-out basis; consequently the last cell in sequence is referred to as the Head of Line (“HoL”) cell.
Referring to
FIG. 1
, this architecture employs a virtual connection queues stage
100
at the front end. Following the virtual connection queues stage
100
, there is a timing queues stage
102
. Following timing queues stage
102
, a departure queue stage
104
is used to store the cells. When a cell arrives, it will be appended to a virtual connection queue based on its connection identifier which is determined by its virtual channel identifier and virtual path identifier. According to this cell's traffic contract, its departure time will be calculated by the algorithm commonly known in the prior art as associated dual leaky buckets. According to its assigned departure time, the cell is then appended to one of time queues shown in FIG.
2
. Once real time pointer
214
points to a timing queue, all cells in the queue are appended to the departure queue
216
which for example would include cells
212
,
210
and
208
, where cells
212
all came from one timing queue and cells
210
all came from a second timing queue.
In the direct exact sorting architecture of the prior art, all cells with the same departure time are appended to the same timing queue, so the departure time of a cell becomes the sequence number indicating the timing queue to which the cell will be appended. This timing queue technology reduces the implementation complexity of the exact sorting of the time stamps. In particular, it avoids comparison and insertion operations which are time consuming.
In order to physically implement the direct exact sorting architecture of the prior art, the number of the timing queues can not be infinite. As a result, it is necessary to reuse the timing queue sequence numbers corresponding to the time stamps. As shown in
FIG. 2
, there are M timing queues including timing queues
200
,
202
,
203
,
204
and
206
. These timing queues must deal with connections that have a variety of cell rates. If rate_max is the maximum cell rate and rate_min is the minimum cell rate, the real time pointer must satisfy two conflicting objectives. First, the real time pointer must be moving at a rate of at least rate_max in order to service the connection with the maximum cell rate. (The rate of the real time pointer is measured in terms of timing queues per second.) Second, the departure time of the cells with the minimum cell rate must not be so much further in the future (that is, 1/rate_min) than the current state of the real time pointer that there is no appropriate timing queue to which the cell may be appended. These two objectives will be satisfied if (a) M is greater than or equal to rate_max/rate_min and (b) the rate of real time pointer is rate_max
Klauber & Jackson
New Jersey Institute of Technology
Sam Phirin
LandOfFree
Method and system for a hierarchical traffic shaper does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for a hierarchical traffic shaper, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for a hierarchical traffic shaper will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3263153