Multiplex communications – Communication techniques for information carried in plural... – Adaptive
Reexamination Certificate
1998-06-19
2002-03-12
Luther, William (Department: 2664)
Multiplex communications
Communication techniques for information carried in plural...
Adaptive
C370S236000, C370S400000
Reexamination Certificate
active
06356565
ABSTRACT:
The invention relates to managing data streams in shared access local area networks, for example networks known under the names Ethernet or Token Ring, and interconnected with extended networks such as the Internet.
BACKGROUND OF THE INVENTION
The occupancy loading of a local network is conventionally managed by subdividing or segmenting its transmission capacities, with the network administrator allocating bandwidths statistically or dynamically as a function of the sizes of the applications loadings expected from the various stations of the network and as a function of the available resources.
The problem posed is to provide every network element (local network, router, applications system) or application of such a network with the ability at all times to transmit data streams with high quality of service, i.e. with an error rate that is as low as possible, and with minimum transmission time, regardless of the data stream loading of the application to be transmitted, and regardless of the occupancy states of the network and of the other interconnected network elements.
The quality of service provided by prior art protocols results directly from the acceptance capacity of the network which is shared in egalitarian manner between all users. This level corresponds to that which is commonly referred to as “best effort”, and is offered to all data streams on the same network without taking other streams into account.
Centralized management protocols have been developed to manage data transmission, such as that described in the article by Y. Bernet, R. Yavatkar, and D. Hoffman, entitled “A proposal for admission control over Internet”, published on the Internet by IETF (Internet engineering task force) under the name <draft-yavatkar-sbm-ethernet-03.txt> in its version of February 1997. These protocols are known under the initials SBM (subnet bandwidth management). The management obtained by such protocols remains completely dependent on a central managing site whose role is to share available resources in terms of bandwidth. Centralized management makes network operation vulnerable to error or breakdown of the central site.
A localized management service is described, for example, in the article by J. Wroclawski entitled “Specification of the controlled-load network element service” published on the Internet by IETF under the name <draft-ietf-intersv-ctrl-load-svc-04.txt> in its November 1996 version. Such a service controls a set of token bucket filters disposed at the interface between each application and a network element. That protocol makes it possible to provide bandwidth by allocating bands via queues through which data passes, as a function of the predetermined characteristics of the token buckets.
Those protocols depend on other information interchange mechanisms, such as the RSVP protocol, for example (resource reservation setup protocol).
The quality of service of such management using a decentralized protocol is substantially of the best effort type, with the various applications sharing the same available resources. Packets that do not comply with the parameters, and processed in best effort mode, are at best deferred, with rates being limited to a maximum value and packets of sizes greater than said value are refused.
Such a protocol defines a “controlled-load” service: it can process packets that do not comply with the parameters of the bucket, it can delay packets that result from distortions and that may be deemed out of compliance in order to be able to pass through the filter; however it refuses data packets of a size greater than the reference size of the bucket. At each network element, e.g. of an Ethernet network, it is then necessary to provide a maximum value for the stream rates of each application, even though that does not guarantee there will be no collisions or no loss of information packets.
A token bucket filter has a bucket with parameters adapted to best effort mode for streams of standard data packets, and buckets with parameters adapted to each stream of data packets having special or privileged specifications in order to enable the various streams to be put into queues and transmitted to the outputs from the buckets as a function of network availabilities.
Those solutions do not solve the problem posed, in particular they do not make it possible to manage band allocation as a function of network occupancy loading and with high quality of service.
OBJECTS AND SUMMARY OF THE INVENTION
To solve this problem, the present invention proposes implementing a decentralized management protocol that, at all times, shares out optimized allocation by adapting the loading of the applications streams to be transmitted to the bandwidths available on the network.
More precisely, the invention provides a method of managing allocated bandwidths of a shared access local network comprising applications stations, switching buses and data transmissions, and token bucket filters as output interfaces between the applications stations and the bus for transmission to the network. The method comprises the following steps:
each network element broadcasts to each of the other network elements, via connections through the protocol, the reserved bandwidths of the data streams to be transmitted (for best effort mode and for privileged odes);
each network element then determines a value of a parameter measuring the bandwidth available for its connection, for which purpose each network element establishes a table of the parameter values transmitted in the preceding step; and
the network element adjusts the value of its best effort parameter as a function of variation in its available bandwidth parameter so as to preserve a positive or zero value therefor.
This method is compatible with using the IP protocol (Internet protocol) for the connections of the shared local network to other networks or to extended networks. This method can also take advantage of using RSVP with which it is compatible.
When a reservation request is made, the management method of the invention may include additional steps in order to decide whether to accept or reject the corresponding reservations, said steps comprising:
comparing the values of the best effort parameters with their minimum value, a new element being unacceptable if all of the best effort parameters are already at their minimum value r
min
since the availability parameter r
fr
of the new element is then necessarily negative;
accepting the reservation increase &Dgr;r of a privileged stream if it is less than or equal to the availability parameter r
fr
of the element; and
refusing said reservation increase if:
it satisfies the condition: &Dgr;r >&Sgr;(r
pr
+r
min
)
at least one of the recalculated availability values r
fr
remains negative after decreasing the best effort parameters.
Other additional steps can be added in order to take account of special situations or to optimize the sharing of reservations:
if two elements require the same increase of reservation simultaneously, then the requests can be rejected even though one of them alone would have succeeded; it is possible to provide for reservation applications to be repeated randomly in time;
when the best effort mode queue is overloaded, r
a
can be increased by decreasing the availability parameter r
fr
, e.g. by making 50% of the value of r
fr
available;
if the real value of the rate parameter in best effort mode is significantly smaller (e.g. more than 10%) than the reservation parameter r
a
, then the parameter r
a
can be decreased to remain close to its real value, thus making it possible to use the band available in best effort mode dynamically, i.e. as a function of requirements; and
when a risk of overload in best effort mode is reasonably predictable, e.g. if numerous packets in privileged mode do not comply with privileged mode format in a particular application, then these packets are sent in best effort mode if no decrease in r
a
is caused thereby.
The invention also relates to a special token bucket filter structure which, in best effort mode
Bouyer Manuel
Horlait Eric
Lahive & Cockfield LLP
Luther William
Universite Pierre et Marie Curie (Paris VI)
LandOfFree
Method of controlling bandwidth allocation in shared access... 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 of controlling bandwidth allocation in shared access..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of controlling bandwidth allocation in shared access... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2836721