Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1998-07-29
2002-05-07
Marcelo, Melvin (Department: 2733)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S412000, C370S468000
Reexamination Certificate
active
06385169
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to packet switched networks such as the Internet, and more particularly to a method for allocating bandwidth in a packet switched network to a service provider subscriber based on the cost paid by the subscriber to the service provider.
BACKGROUND OF THE INVENTION
The Internet is an example of a packet switched network in which individual packets are treated as independent datagrams on a best-effort model that are serviced on a FIFO basis. The best-effort model does not provide any form of traffic isolation among different users, however, and thus resources are shared only on the basis of how much bandwidth a user requests. Accordingly, adequate Internet functioning depends on the cooperation of hosts end systems such as TCP congestion control mechanisms. Reliance on the cooperation of the host end systems is increasingly becoming unrealistic. Inevitably, users attempt to exploit the weakness of the best-effort model to gain more resources. For example, Netscape's browser allows users to open multiple TCP connections. Moreover, with the best-effort model it is impractical to guarantee a quality of service level, either in terms of an absolute or relative amount of bandwidth, because all traffic is integrated into a single datastream or flow.
Quality of service (QoS) alternatives to the best effort model have been extensively studied. Many of the alternatives are based on the reservation of resources on an end-to-end basis prior to establishing communication. Examples of such alternatives include RSVP and Int-Serv, which are discussed, for example, in L. Zheng, S. Deering, S. Estrin, S. Shenker, D. Zappala, “A New Resource Reservation Protocol”, IEEE Network, September 1993. While the architectures of the various proposals differ in details, the underlying models generally employ an application-oriented approach in which applications make resource reservations on an end-to-end and per session basis. This approach achieves QoS guarantees by performing the following steps. First, the particular application characterizes its traffic in probabilistic (e.g., equivalent bandwidth) or a deterministic (e.g., leaking bucket) profile and describes its requirements in a flow specification. Based on these requirements, one or more potentially satisfactory paths through the network are found. Next, a reservation/signaling protocol installs the reservation over the potential path on a hop-by-hop basis, assuming that the call admission control at each hop permits the reservation to be made.
However, end-to-end resource reservation methods encounter a number of problems when implemented over the Internet. For example, it is difficult for an application to accurately characterize traffic on an a priori basis. The traffic of a video source, for example, can be highly content-dependent. Additionally, end to end resource reservation methods do not work well for applications based on the World Wide Web, which are often characterized by sessions of very short duration. For applications with long lasting sessions, such as video conferences, the delays and overhead caused by the reservation process is minimal. However, for sessions of short duration there is a high overhead associated with establishing a reservation for each session and is thus much less useful.
Another problem with end-to-end resource reservation methods is that each reservation requires a separate service contract between the user and the network. Such on-demand per-session contracting has a high administrative overhead. Also, there is substantial complexity involved in the settling of accounts among different Internet service providers. When a path traverses multiple ISPs, an end-to-end reservation requires an agreement among all the major ISPs involved. Any given ISP that does not participate in such an agreement may prevent the reservation from being made. Finally, end-to-end resource reservation methods do not scale well as the number of reservations increases. Since the number of reservations that is required increases linearly with the number of active application sessions traversing a link, the signaling process involved in establishing the reservation can become a bottleneck.
Other approaches to Internet traffic generally fall into two categories: the profile-based tagging model and the delay priority model. In the profile-based tagging model, each user and its respective ISP agree on a profile of traffic to be given routed in an expedited manner. When the traffic entering the domain of the ISP exceed a specified profile, the excess packets are admitted but tagged. If congestion arises within the ISP's domain, the routers will begin to disregard packets, starting with the tagged packets. That is, profile-based tagging essentially creates two categories of traffic: tagged and untagged. The tagged traffic is treated in a FIFO fashion. A misbehaving source may still gain more bandwidth simply by injecting excessive traffic. This problem can be aggravated when the fixed profiles are significantly above (or below) the level appropriate for the congested links. In such a case the majority of the packets are not tagged (or are tagged). Thus, tagging provides little information to enforce differentiation and the network behavior essentially defaults to something similar to a simple FIFO best effort model.
The delay priority model represents an extreme form of resource allocation in which the lower priority classes suffer all the consequences of congestion. Unless the priority traffic only accounts for a very small percentage of the link capacity, lower priority traffic may experience significant deterioration under congestion, and may in fact fail to receive any bandwidth whatsoever. In fact, TCP has the tendency to utilize as much bandwidth as it can. Because the congestion is invisible to the higher priority traffic, the network no longer provides any indication of congestion to the higher priority traffic. Thus, TCP windows in the higher priority classes may expand until there is no bandwidth available to the lower priority traffic.
The end-to-end model and the best effort model represent two extremes along a spectrum of the previously mentioned approaches. That is, the best effort model provides no traffic isolation while the end-to-end model provides isolation at the finest level of granularity, that of an individual connection. Presumably, an appropriate solution lies somewhere between the two extremes.
Accordingly, it would be desirable to allocate network resources by selecting an appropriate level of granularity for isolating traffic that better satisfies the needs of both the users and the service providers and which is also scalable as the Internet continues to grow.
SUMMARY OF THE INVENTION
The present invention provides a method for allocating bandwidth to a subscriber in a service provider domain that is part of a packet switched network such as the Internet, for example. In accordance with the method, a number of shares of bandwidth are assigned to the subscriber based on a contractual agreement between the subscriber and the service provider. A subscriber identifier and the number of shares assigned thereto are distributed to the routers in the domain of the service provider. The routers will in turn allocate bandwidth to packets they receive based on the number of shares assigned to the subscriber transmitting or receiving the packet. The subscriber may include one or more different user terminals that aggregate traffic onto a single datastream. The shares assigned to the user may denote an absolute amount of bandwidth, or alternatively, may denote a relative bandwidth allocation.
In accordance with another aspect of the invention, a method is provided for routing packets of traffic in a packet switched network, which are received by a service provider. The service provider first determines if a received packet has a source or destination address belonging to a subscriber of the service provider and, if so, the service provider determines a pr
Marcelo Melvin
Mayer Stuart H.
LandOfFree
Allocation of bandwidth in a packet switched network among... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Allocation of bandwidth in a packet switched network among..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Allocation of bandwidth in a packet switched network among... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2878212