Browse Prior Art Database

Optimal Compression and Routing in Networks

IP.com Disclosure Number: IPCOM000121208D
Original Publication Date: 1991-Aug-01
Included in the Prior Art Database: 2005-Apr-03
Document File: 3 page(s) / 111K

Publishing Venue

IBM

Related People

Cahn, RS: AUTHOR

Abstract

Described is a method whereby an optimal path and optimal placement of compressors and decompressors is provided for communication networks routing. So as to improve the performance of communication networks, the optimal routing and location the compressors and decompressors is transformed into finding the least cost path in a directed graph.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 51% of the total text.

Optimal Compression and Routing in Networks

      Described is a method whereby an optimal path and optimal
placement of compressors and decompressors is provided for
communication networks routing.  So as to improve the performance of
communication networks, the optimal routing and location the
compressors and decompressors is transformed into finding the least
cost path in a directed graph.

      Typically, communication networks provide a routing service
since the mechanisms for ARPANET, TCP/IP SNA and DNA are readily
available [1]. Routing often involves the use of a shortest path
routing algorithm; however, the network routing algorithms often do
not consider the effect of data compression on the routing or the
routing on the data compression.  The concept described herein
considers the compression factor in the formulation of the network
routing algorithms.

      Data compression algorithms come in a variety of types. At one
end of the spectrum are algorithms to compress speech.  At the other
end are algorithms which provide lossless compression suitable for
data networks.  The algorithms derived in the concept described
herein provides a means of computing the optimal routing and location
of compressors and decompressors in a network, given the session
type, link costs, and the cost and availability of the compression
resources.

      Assuming that the types of available compression in the network
are represented by a tree T.  The root of the tree represents
uncompressed or raw data.  The leaves of the tree represent terminal
compression algorithms and the intermediate nodes represent partial
compression.  It is often possible to compress by stages.  In
lossless compression, one might first compress by means of run length
encoding and then compress by using a Lempel-Ziv algorithm. If the
network provides connection- oriented services, then these may be
provided by fixed routing, as in SNA, or the PSTN, or by per-packet
routing, as in ARPANET and DNA.  In the latter case, there is no
option but to compress at the source and decompress at the
destination.  In the former case, it is possible to position the
compression anywhere along the route.  In the next section, the
algorithm is developed which computes the least cost of compression
plus transmission between a source and a destination.  The
calculation can be performed at a session set-up and need not be
statically defined.

      Assuming that a network consists of nodes N and links L, for a
given session type S, only the compression techniques TS C T apply.
Without loss of generality, it is assumed that TS=T in the rest of
the section.  Each compression, t in the tree T reduces the data to
be transmitted by a factor of a1t,S and should be thought of as a
long- term measure of the power of the compression technique.  It may
be deterministic, as with ADPCM, or approximate, as with Huffman
encoding. The cost of transmitting a bit of data across nod...