Redundant routing with deadlines in data networks

Details Redundant routing with deadlines in data networks Redundant routing with deadlines in data networks

1999-08-05

2003-12-09

Kizou, Hassan (Department: 2662)

Multiplex communications

Data flow congestion prevention or control

Control of data admission to the network

C370S236000, C370S252000, C370S255000, C370S390000, C370S395100, C370S412000, C709S241000, C709S238000

Reexamination Certificate

active

06661775

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to the field of computer networks and, more particularly to redundant routing with deadlines for providing an expected quality of service (QoS) guarantee in packet-switching computer networks.
2. Description of the Related Art
Currently, the architecture of the Internet provides a simplistic service model known in the art as the point-to-point best service model. The point-to-point best service model, however, is inadequate for some of today's every developing complex distributed applications such as, for example, remote video and Internet conferencing applications. It has been determined by various scholars that the inadequacy stems in part from the failure of the point-to-point best service model to provide acceptable quality of service (QoS) to the data packets of these developing applications.
These newer and much more complex applications are extremely sensitive to the QoS that their data packets receive and the network servicing these application must go beyond the best-effort model to provide an acceptable QoS. L. Zhang et al., in RSVP: A New Resource ReSerVation Protocol, IEEE Network, September 1993, have proposed a reservation-based (RSVP) technique to ensure QoS over the Internet. Briefly, the RSVP technique allows applications to request network resources, such as bandwidth, to fulfill desired QoS requirements. Reservations are initiated at the information receivers and are carried to the routers along the communication path to the sender of the data destined for the receiver.
Other reservation-based techniques, similar to the technique described by L. Zhang et al., have also been proposed, The reservation-based approaches to QoS are sometimes collectively referred to as integrated-services or intserv. Although reservation-based techniques provide benefits that are not obtainable using the point-to-point best-effort model, they are not without their shortcomings. For example, these approaches rely on “good” estimates and scheduling of the buffer and bandwidth requirements needed to meet the QoS demands, which can be quite complex for bursty data traffic. That is, reservation-based techniques introduce additional complexity at the network nodes and require strict queuing schemes to ensure perflow (flow is the generic term often used to describe a network data traffic stream) processing with specified service requirements. Furthermore, reservation-based techniques require perflow state information and management at the routers, which may cause network scalabilty problems. Accordingly, it is believed that increasing the complexity of intermediate nodes to perform advanced operations will transform the nodes into bottlenecks in high-speed networks such as the Internet and are thus, undesirable.
As an alternative to the reservation-based or intserv based approaches to QoS, a new approach known in the art as differential services or diffserv has been proposed. The diffserv approach aims at reducing the perflow management and complexity at the high-speed routers associated with the intserv approaches. Examples of diffserv based approaches are described by D. Clark and J. Wroclawski, in An Approach to Service Allocation in the Internet, Internet Draft, July 1997 and K. Nichols et al., in A Two-bit Differentiated Services Architecture for the Internet, Internet Draft, November 1997. The main idea behind diffserv is to provide an aggregated treatment of user traffic that belongs to the same service class.
In some diffserv models, a non-deterministic assured level of service based on statistical provisioning specified in a service profile is provided, while in other diffserv models a premium based service based on peak-rate provisioning is provided. In both cases, user traffic is marked before it enters the network to indicate whether or not it follows the service description of the class. The packets that are not within the user's service description are the first ones dropped during periods of traffic congestion. Guaranteed QoS can not be provided because the model can not determine what other users in the network are doing. Although diffserv is a more scalable approach than intserv, it still requires reservations (i.e., reservations are made before entering the network boundary via a contract as opposed to marking the routers inside the network), which as noted above, is undesirable. Accordingly, there is a need and desire to efficiently provide a QoS guarantee in high-speed packet-switching data networks, such as the Internet that is not reservation-based.
SUMMARY OF THE INVENTION
The present invention provides a probabilistic quality of service in a high-speed packet-switching data network, such as the Internet that is not reservation-based.
The above and other features and advantages of the invention are achieved by a method and message router that breaks up files to be transferred over a network connection within a specified deadline into fixed-sized pieces. Each piece contains enough redundant information so that a subset (but not all) of the pieces will be sufficient to construct the file at the destination. The method and router determine optimal values for the number of pieces the file should be split into and the subset of pieces required to reconstruct the full contents of the file in order to maximize the probability that the file can be reconstructed at the destination by the specified deadline. The method and router provide an expected QoS guarantee by using redundancy with a deadline rather than reservations.


REFERENCES:
patent: 5732218 (1998-03-01), Bland et al.
patent: 5831975 (1998-11-01), Chen et al.
patent: 5991414 (1999-11-01), Garay et al.
patent: 5995503 (1999-11-01), Crawley et al.
patent: 6122254 (2000-09-01), Aydemir et al.
patent: 6233226 (2001-05-01), Gringeri et al.
patent: 6400685 (2002-06-01), Park
M.O. Rabin, Efficient dispersal of information for security, load balancing, and fault tolerance. Jrn. ACM, 36-2:335-348, 1989.
Bolot et al., “Adaptive FEC-Based Error Control for Internet Telephony”, 8 pages.
S. Jamaloddin Golestani et al, To appear in Proceed. Of ICNP, Oct. 98, “A Class of End-to-End Congestion Control Aigoriths for the Internet.”
D. Clark and J. Wroclawski. “An approach to service allocation in the internet.” Internet Draft, page Jul., 1997.
David D. Clark et al. “Explicit Allocation of Best Effort Packet Delivery Service.”
V.P. Kumar et al., “Beyond Best Effort: Router Architectures for the Differentiated Services of Tomorrow's Internet”.
Ion Stoica et al.; “LIRA: An Approach for Service Differentiation in the Internet.”
Lixia Zhang et al., “RSVP: A New Resource ReSerVation Protocol”; IEEE Network, Sep. 1993.
K. Nichols et al.; “A Two-bit Differenntiated Services Architecture for the Internet”; Internet Draft, Page Nov. 1997.

Affiliated with

Also associated with

Rating

Redundant routing with deadlines in data networks does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Redundant routing with deadlines in data networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Redundant routing with deadlines in data networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3101376