Browse Prior Art Database

On packet switches with infinite storage (RFC0970)

IP.com Disclosure Number: IPCOM000004966D
Original Publication Date: 1985-Dec-01
Included in the Prior Art Database: 2001-Jul-12
Document File: 10 page(s) / 24K

Publishing Venue

Internet Society Requests For Comment (RFCs)

Related People

J. Nagle: AUTHOR

Abstract

Most prior work on congestion in datagram systems focuses on buffer management. We find it illuminating to consider the case of a packet switch with infinite storage. Such a packet switch can never run out of buffers. It can, however, still become congested. The meaning of congestion in an infinite-storage system is explored. We demonstrate the unexpected result that a datagram network with infinite storage, first-in-first-out queuing, at least two packet switches, and a finite packet lifetime will, under overload, drop all packets. By attacking the problem of congestion for the infinite-storage case, we discover new solutions applicable to switches with finite storage.

This text was extracted from a ASCII document.
This is the abbreviated version, containing approximately 13% of the total text.

Network Working Group John Nagle Request for Comments: 970 FACC Palo Alto

December 1985

On Packet Switches With Infinite Storage

Status of this Memo

The purpose of this RFC is to focus discussion on particular problems in the ARPA-Internet and possible methods of solution. No proposed solutions in this document are intended as standards for the ARPA-Internet at this time. Rather, it is hoped that a general consensus will emerge as to the appropriate solution to such problems, leading eventually to the adoption of standards. Distribution of this memo is unlimited.

Abstract

Most prior work on congestion in datagram systems focuses on buffer management. We find it illuminating to consider the case of a packet switch with infinite storage. Such a packet switch can never run out of buffers. It can, however, still become congested. The meaning of congestion in an infinite-storage system is explored. We demonstrate the unexpected result that a datagram network with infinite storage, first-in-first-out queuing, at least two packet switches, and a finite packet lifetime will, under overload, drop all packets. By attacking the problem of congestion for the infinite-storage case, we discover new solutions applicable to switches with finite storage.

Introduction

Packet switching was first introduced in an era when computer data storage was several orders of magnitude more expensive than it is today. Strenuous efforts were made in the early days to build packet switches with the absolute minimum of storage required for operation. The problem of congestion control was generally considered to be one of avoiding buffer exhaustion in the packet switches. We take a different view here. We choose to begin our analysis by assuming the availablity of infinite memory. This forces us to look at congestion from a fresh perspective. We no longer worry about when to block or which packets to discard; instead, we must think about how we want the system to perform.

Pure datagram systems are especially prone to congestion problems. The blocking mechanisms provided by virtual circuit systems are absent. No fully effective solutions to congestion in pure datagram systems are known. Most existing datagram systems behave badly under overload. We will show that substantial progress can be made on the

Nagle [Page 1]

RFC 970 December 1985 On Packet Switches With Infinite Storage

congestion control problem even for pure datagram systems when the problem is defined as determining the order of packet transmission, rather than the allocation of buffer space.

A Packet Switch with Infinite Storage

Let us begin by describing a simple packet switch with infinite storage. A switch has incoming and outgoing links. Each link has a fixed data transfer rate. Not all links need have the same data rate. Packets arrive on incoming links and are immediately assigned an outgoin...