Electricity: battery or capacitor charging or discharging – Serially connected batteries or cells – With discharge of cells or batteries
Reexamination Certificate
1999-10-15
2003-03-25
Chin, Wellington (Department: 2664)
Electricity: battery or capacitor charging or discharging
Serially connected batteries or cells
With discharge of cells or batteries
C209S238000
Reexamination Certificate
active
06538416
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to resource reservations within a distributed network. It finds particular application in conjunction with setting-up and maintaining reservations within the Internet, and will be described with particular reference thereto. It will be appreciated, however, that the invention is also amenable to other like applications.
A resource reservation enables guaranteed communication between end-to-end resources (e.g., a source and a destination). Such guaranteed communication is critical for time-sensitive applications including Internet telephony, multimedia-on-demand, and interactive computer games.
The deployment of inter-domain resource reservations in the Internet has been delayed by the desire of each carrier to control its own routing and resource management policies. Carriers appear to prefer having relatively narrow interfaces to the rest of the Internet. One drawback to such narrow interfaces is that they only present a limited amount of network connectivity and resource sharing information at a network's borders.
The size of the Internet has grown rapidly over the past several years. This growth is expected to continue into the future. As the Internet grows, the processes involved with creating and maintaining resource reservations across the network become more complicated. The increased complexity tends to slow down the formation of resource reservations and requires more network resources for maintaining the reservations once they are created. Therefore, it is desirable to scale resource reservation protocols with the size of the Internet.
Inter-domain resource reservations must satisfy a number of criteria in order to scale with the expanding Internet. More specifically, resource reservations must reduce the storage of reservation information, reduce the cost of processing reservation messages, reduce the bandwidth consumed by reservation information, and simplify the delivery commitments to peering domains.
Routers store reservation control information tables and packet classifier tables. The size of these tables is typically a function of the number of end users n. In conventional systems, the reservation control information tables and packet classifier tables include n
2
entries. Considering the growth of the Internet, such table sizes are becoming unmanageable.
The cost of processing reservation messages depends on the complexity of handling each message and the frequency of reservation messages. Conventional end-applications set-up reservations across domains. Therefore, reservation updates are relatively frequent. Along with increasing Internet traffic, frequent reservation updates also increase the cost of processing reservation messages.
Ideally, bandwidth consumed by reservation information exchange is small relative to the link bandwidth, both in steady state and with routing transients. This bandwidth overhead is typically proportional to the number of states kept in routers. Because the number of states kept in the routers is n
2
(where n is the number of users), bandwidth overhead is becoming a significant factor as the Internet continues to grow.
It is desirable that each domain manage its own network resources and enforce its own internal traffic engineering policies. This implies that a domain only reveals simple delivery commitments to its peering domains. The inter-domain reservation then uses these delivery commitments to establish a reservation path through multiple domains. Each domain sets-up transit reservation flows using its preferred intra-domain reservation mechanism. As the Internet grows, a need exists for connecting multiple reservation segments from various domains together in a more efficient manner.
Both router-based and server-based systems have presented scalable resource reservations. However, as discussed below, these systems include various drawbacks.
Current router-based approaches are available that modify the conventionally used reservation protocol (“RSVP”) to support scalable reservations. These router-based approaches allow routers to aggregate individual reservation requests. However, they do not address state storage scaling issues (e.g., aggregated reservations are received in RSVP Sender Template and Session pairs). Furthermore, these conventional router-based approaches set-up reservations between every pair of domains that communicate via reserved flows. Therefore, the storage states scale as a function of the square of the communicating domains. Given that there are currently more than 4,500 domains, such a condition is undesirable.
In current server-based approaches, a bandwidth broker (or agent) in each domain is responsible for selecting and setting-up aggregated reservation sessions. This approach has the advantage of removing message processing and storage burdens from the routers. However, synchronizing reservation information among the bandwidth brokers and the border routers is a complex process. Furthermore, the processing overhead remains (and is simply moved to a different network entity). Also, there is a potential that a new single point of failure for the entire domain is introduced.
Two-tier reservation models have also been proposed. In these models, intra-domain reservation protocols are used within a domain to set-up reserved flows between senders and receivers. Inter-domain reservation protocols set-up coarsely-measured reserved flows between domains. Although two-tier models have been proposed, the actual mechanisms for implementing these models have not been defined.
The present invention provides a new and improved apparatus and method which overcomes the above-referenced problems and others.
SUMMARY OF THE INVENTION
A method creates a reserved communication tree for state aggregation. A stateless probe, which requests a specified bandwidth, is sent from a leaf router toward a root router within a network. The stateless probe discovers a communication path, potentially including intermediate routers, between the leaf router and the root router. A graft message is returned from the root router to the leaf router along the communication path. A bandwidth reservation is created within each of the routers through which the graft message travels. Each of the bandwidth reservations is as large as the specified amount and is associated with an adjacent router in the communication path. A reserved communication path is established within the network. The reserved communication path includes the root router, any of the intermediate routers, the leaf router, and a bandwidth reservation for each of the routers along the reserved communication path. The established communication path is aggregated with other established communication paths to form a reserved communication tree.
One advantage of the present invention is that it aggregates individual reservation requests.
Another advantage of the present invention is that it scales, in terms of state storage, processing, and bandwidth, as a function of the number of communicating domains.
Still further advantages of the present invention will become apparent to those of ordinary skill in the art upon reading and understanding the following detailed description of the preferred embodiments.
REFERENCES:
patent: 5987018 (1999-11-01), Freeburg et al.
patent: 6091737 (2000-07-01), Hong et al.
patent: 6141319 (2000-10-01), Dighe et al.
patent: 6185210 (2001-02-01), Troxel
patent: 6343326 (2002-01-01), Acharya et al.
patent: 6449647 (2002-09-01), Colby et al.
patent: 6466985 (2002-10-01), Goyal et al.
D. Awduche, L. Berger, D. Gan, T. Li, G. Swallow, and V. Srinivsan, “Extensions to RSVP for LSP Tunnels,” Internet Draft, Internet Engineering Task Force, Nov. 1998. Work in progress.
S. Herzog, R. Guerin, and S. Blake, “Aggregating RSVP-based QoS Requests,” Internet Draft, Internet Engineering Task Force, Nov. 1997. Work in progress.
L. Zhang, S. Deering, D. Estrin, S. Shenker, and D. Zappala, “RSVP: A New Resource ReSerVation Protocol,”IEEE Network,vol. 7, pp. 8-18, Sep. 1993. OCLC 14393593 ISSN 0890-80
Hahne Ellen L.
Pan Ping P.
Schulzrinne Henning G.
Chin Wellington
Fay, Sharpe, Beal, Fagan, Minnich & McKee
Jones Prenell
Lucent Technologies - Inc.
LandOfFree
Border gateway reservation protocol for tree-based... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Border gateway reservation protocol for tree-based..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Border gateway reservation protocol for tree-based... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3079880