Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

1999-01-01

Filename

WUCS-99-27.PDF

Technical Report Number

WUCS-99-27

Abstract

Current IP routers are stateless: they forward individual packets based on the destination address contained in the packet header, but maintain no information about the application or flow to which a packet belongs. This stateless service model works well for best effort datagram delivery, but is grossly inadequate for applications that require quality of service guarantees, such as audio, video, or IP telephony. Maintaining state for each flow is expensive because the number of concurrent flows at a router can be in the hundreds of thousands. Thus, stateful solutions such as Intserv (integrated services) have not been adopted for their lack of scalability. Motivated by this dilemma, we formulate and solve the flow aggregation problem, where we give an efficient algorithm for computing the smallest set of aggregated flows that encode the forwarding state of individual flows. Our hope is that such aggregation of state information might increase the viability of Intserv-type protocols.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7ZP44CX

Download

Share

COinS