Dynamic Packet State (DPS)

Dynamic Packet State (DPS) is a general and powerful technique that can be used to provide scalable network services in a network domain in which interior nodes maintain no per flow state. More precisely, DPS can provide services with levels of flexibility, utilization, and assurance similar to those that can be achieved with per flow mechanisms.

With Dynamic Packet State, each packet carries in its header some state. which is initialized by the ingress node. Interior nodes process each incoming packet based on the state carried in the packet's header, updating both its internal state and the state in the packet's header before forwarding it to the next hop. By using DPS to coordinate actions of edge and interior nodes along the path traversed by a flow, distributed algorithms can be designed to approximate the behavior of a broad class of "stateful" networks using networks in which interior nodes do not maintain per flow state.

Internet Draft

The following document proposes a family of Per Hop Behaviors (PHBs) based on DPS in the context of the differentiated service architecture. The document describes several services that can be implemented by PHBs based on DPS. These include weighted fair share service, penalty box service, guaranteed service (with mathematically proven worst case bounds), and distributed bandwidth broker service. The document also discusses possible solutions for encoding Dynamic Packet State that have the minimum incompatibility with IPv4.

Per Hop Behaviors Based on Dynamic Packet State [ draft-stoica-diffserv-dps-00.txt]

Related Talks

Talk at IETF ISSLL Meeting, March 1999. [.ps] [.pdf]
Talk at Internet End-to-End Research Meeting, June 1999. [.ps.gz]

Related Papers using the DPS Technique

Support for congestion control and traffic management. Router mechanisms designed to achieve fair bandwidth allocations, like Fair Queueing, have many desirable properties for congestion control in the Internet. In this work we use DPS to approximate fair allocations at all nodes of the network, and thus provide a highly scalable solution for congestion control.
- Core-Stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks
  - paper [.ps.gz] [.pdf] ` in Proceedings of ACM SIGCOMM'98, Vancouver, Canada, pp. 118-130
  - technical report CMU-CS-98-136 [.ps.gz],
  - presentation slides [.html] [.ps.gz] [.pdf]
  - web page [.html]
Differentiated services for traffic aggregates with large spatial granularitie. This paper proposes an assured service model, which uses DPS to approximate the functionality of a network in which each user can control its allocations on network's links in order to maximize its overall throughput.
- LIRA: An Approach for Service Differentiation in the Internet
  - paper [.ps.gz] [.pdf] in Proceedings of NOSSDAV'98, Cambridge, England.
  - presentation slides [.html] [.ps.gz] [.pdf]
  - web page [.html ]
Per flow QoS guarantees. This example demonstrates that, by using DPS, it is possible to provide Intserv guaranteed service semantic without performing per flow management at interior nodes.
- Providing Guaranteed Services Without Per Flow Management
  - paper [.ps.gz] [.pdf], Proceedings of ACM SIGCOMM'99, BOSTON, MA, September 1999, pp. 81-94.
  - technical report CMU-CS-99-133 [.ps.gz],
  - presentation slides [ .ps.gz] [ .pdf]
  - web page [.html

istoica@cs.cmu.edu