Data segmentation within a renegotiated bit-rate service transmission system

• US 5,559,798 A
• Filed: 04/19/1995
• Issued: 09/24/1996
• Est. Priority Date: 04/19/1995
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Keshav, Srinivasan, Tse, David, Grossglauser, Matthias, Clarkson, Kenneth L.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Patel, Ajit
• Application Number:
  US08/424,838
• Time in Patent Office: 524 Days
• Field of Search: 370/60, 370/60.1, 370/58.1-58.3, 370/84, 370/85.7, 370/94.1, 370/94.3, 370/95.1, 370/95.3, 370/112, 370/77, 370/79, 370/91, 370/92, 370/110.1
• US Class Current: 370/468
• CPC Class Codes: H04L 2012/5638 Services, e.g. multimedia, GOS, QOS
• CPC Class Codes: H04L 2012/5639 Tariffs or charging
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04N 21/236 Assembling of a multiplex stream, e.g. transport stream, by combining a video stream with other content or additional data, e.g. inserting a URL [Uniform Resource Locator] into a video stream, multiplexing software data into a video stream; Remultiplexing of multiplex streams; Insertion of stuffing bits into the multiplex stream, e.g. to obtain a constant bit-rate; Assembling of a packetised elementary stream multiplexing of data packets for data networks, e.g. RTP/UDP H04L65/00
• CPC Class Codes: H04N 21/434 Disassembling of a multiplex stream, e.g. demultiplexing audio and video streams, extraction of additional data from a video stream; Remultiplexing of multiplex streams; Extraction or processing of SI; Disassembling of packetised elementary stream demultiplexing of data packets for data networks, e.g. RTP/UDP H04L65/00
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A system and method for the segmentation of data exhibiting an intrinsic long-term average data rate, punctuated with periods of peak rate data bursts. This segmentation conditions the data for efficient transmission via either a renegotiated constant bit-rate ("RCBR") network or a renegotiated variable bit-rate network ("RVBR") network. Within these networks, data transmission rates between a sender and a recipient are rapidly renegotiated as a function of previously stored data transmission demand information and system buffer levels. Such a system is responsive to the rate at which new calls or requests for connections enter and leave the network, the frequency and duration of extended peak rate data bursts, as well as the occurrence of short duration data transmission peaks.

Claims

1. A data transmission system comprising:

a first site, including a first memory storing a series of data segments, and a second memory storing a previously compiled record of instantaneous transmission rates, each of said stored rates being associated with one or more of said stored data segments;

a second site;

a variable bit-rate network providing a connection between said first and said second sites;

a network controller adapted to negotiate a connection between said first site and said second site having a particular bandwidth in response to the contents of said second memory;

a data buffer, interposed between said first site and said variable bit-rate network, and adapted to store a finite amount of data segments; and

a data pre-processor adapted to optimally segment incoming data so as to minimize the cost of negotiating and effecting the transmission of said segmented data from said first site to said second site via said data buffer and said variable bit-rate network, store said optimally segmented data in said first memory, and store a record indicative of the instantaneous transmission rate associated with each of said stored segments in said second memory.

2. The invention of claim 1 wherein said data segments represent a video signal.

3. The invention of claim 1, wherein said cost of negotiating and effecting the transmission of data segments from said first site to said second site via said data buffer and said variable bit-rate network is determined within said data pre-processor on the basis of the cost of modifying the state of said variable bit-rate network, where a given state is defined by bandwidth allocation (k) within said variable bit-rate network during arbitrary interval i, data buffer occupancy (b) during arbitrary interval i, and the partial cost of obtaining the path (w) to the desired variable bit-rate network state.

4. The invention of claim 3 wherein said data segments represent a video signal.

5. The invention of claim 1, wherein said cost of negotiating and effecting the transmission of data segments from said first site to said second site via said data buffer and said variable bit-rate network is determined within said data pre-processor on the basis of the cost of modifying the state of said variable bit-rate network, where a given state is defined by bandwidth allocation (k) within said variable bit-rate network during arbitrary interval i, data buffer occupancy (b) during arbitrary interval i, and the costs incurred during interval i obtaining a portion of the most cost effective path (w) to the final desired variable bit-rate network state.

6. The invention of claim 5 wherein said data segments represent a video signal.

7. A method for processing data for segmented transmission from a first site to a second site via a data buffer and a variable bit-rate network, comprising the steps of:

segmenting data as a function of the cost of negotiating and transmitting segments from said first site to said second site via said data buffer and said variable bit-rate network, wherein said cost for N-1 intervals is calculated as;

##EQU3## where φ

is the cost of performing a network bandwidth renegotiation within said variable bit-rate network, γ

is the cost of utilizing a given amount of bandwidth within said variable bit-rate network for a unit time, r_i is the amount of data processed during an arbitrary interval i, s_i is the service rate required within said variable bit-rate network to effectively transmit data r_i, and ##EQU4## storing said segmented data in a first memory; and

compiling said storing a record of instantaneous transmission rates, each of said stored rates being associated with one or more of said stored data segments.

8. The invention of claim 7 wherein said data segments represent a video signal.

9. The invention of claim 7, wherein said cost of negotiating and transmitting data segments from said first site to said second site via said data buffer and said variable bit-rate network is assessed as a function of the state of said variable bit-rate network;

wherein said state is defined by data comprising information representing an arbitrary interval duration (i), bandwidth allocation (k) within said variable bit-rate network, data buffer occupancy (b), and the partial cost of obtaining the most cost effective path (w) to the next desired variable bit-rate network state.

10. The invention of claim 9 wherein said data segments represent a video signal.

11. The invention of claim 9, wherein said assessment of said cost of negotiating and transmitting data segments from said first site to said second site via said data buffer and said variable bit-rate network, further comprises the following steps:

a) creating an initial set of nodes, each representing a particular state of said variable bit-rate network for an initial interval i=0, and comprising a data set having the form (k0,b0=0,w0=0), where k assumes values from 0 to the maximum bandwidth available within said variable bit-rate network;

b) calculating and creating a record of all possible path portions between the initial node i and i+1 node;

c) calculating the cost of each path portion according to the previously discussed network renegotiation/transmission cost for N-1 intervals as;

##EQU5## where φ

is the cost of performing a network bandwidth renegotiation within said variable bit-rate network, γ

is the cost of utilizing a given amount of bandwidth within said variable bit-rate network for a unit time, r_i is the amount of data processed during an arbitrary interval i, s_i is the service rate required within said variable bit-rate network to effectively transmit data r_i, and ##EQU6## d) pruning all non-optimal path portions, wherein a non-optimal path portion is defined as any path portion X going through a particular node x for a particular interval, where there exists a path portion Y through node y during said particular interval, such that

e) repeating steps c and d until a path to the next desired variable bit-rate network state is completed.

12. The invention of claim 11 wherein said data segments represent a video signal.