Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-10-14
2004-07-06
Patel, Ajit (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S503000
Reexamination Certificate
active
06760328
ABSTRACT:
RELATED APPLICATIONS
FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not Applicable.
BACKGROUND OF THE INVENTION
This invention relates to generally to a method and apparatus for transmitting of data on a communications network. More specifically, this invention relates to timely forwarding and delivery of data over the network and to their destination nodes. Consequently, the end-to-end performance parameters, such as, loss, delay and jitter, have either deterministic or probabilistic guarantees.
The proliferation of high-speed communications links, fast processors, and affordable, multimedia-ready personal computers brings about the need for wide area networks that can carry real-time data, like telephony and video. However, the end-to-end transport requirements of real-time multimedia applications present a major challenge that cannot be solved satisfactorily by current networking technologies. Such applications as video teleconferencing, and audio and video group (many-to-many) multicasting generate data at a wide range of bit rates and require predictable, stable performance and strict limits on loss rates, end-to-end delay bounds, and delay variations (“jitter”). These characteristics and performance requirements are incompatible with the services that current circuit and packet switching networks can offer.
Circuit-switching networks, which are still the main carrier for real-time traffic, are designed for telephony service and cannot be easily enhanced to support multiple services or carry multimedia traffic. Its synchronous byte switching enables circuit-switching networks to transport data streams at constant rates with little delay or jitter. However, since circuit-switching networks allocate resources exclusively for individual connections, they suffer from low utilization under bursty traffic. Moreover, it is difficult to dynamically allocate circuits of widely different capacities, which makes it a challenge to support multimedia traffic. Finally, the synchronous byte switching of SONET, which embodies the Synchronous Digital Hierarchy (SDH), requires increasingly more precise clock synchronization as the lines speed increases [John C. Bellamy, “Digital Network Synchronization”,
IEEE Communications Magazine
, April 1995, pages 70-83].
Packet switching networks like IP (Internet Protocol)—based Internet and Intranets [see, for example, A. Tannebaum,
Computer Networks
(3rd Ed) Prentice Hall, 1996] and ATM (Asynchronous Transfer Mode) [see, for example, Handel et al.,
ATM Networks: Concepts, Protocols, and Applications
(2nd Ed.) Addison-Wesley, 1994] handle bursty data more efficiently than circuit switching, due to their statistical multiplexing of the packet streams. However, current packet switches and routers operate asynchronously and provide best effort service only, in which end-to-end delay and jitter are neither guaranteed nor bounded. Furthermore, statistical variations of traffic intensity often lead to congestion that results in excessive delays and loss of packets, thereby significantly reducing the fidelity of real-time streams at their points of reception.
Efforts to define advanced services for both IP and ATM have been conducted in two levels: (1) definition of service, and (2) specification of methods for providing different services to different packet streams. The former defines interfaces, data formats, and performance objectives. The latter specifies procedures for processing packets by hosts and switches/routers. The types of services that defined for ATM include constant bit rate (CBR), variable bit rate (VBR) and available bit rate (ABR).
The methods for providing different services under packet switching fall under the general title of Quality of Service (QoS). Prior art in QoS can be divided into two parts: (1) traffic shaping with local timing without deadline scheduling, for example [Demers et al., “Analysis and Simulation Of A Fair Queuing Algorithm”,
ACM Computer Communication Review
(SIGCOMM'89), pages 3-12, 1989; S. J. Golestani, “Congestion-Free Communication In High-Speed Packet Networks”,
IEEE Transcripts on Communications
, COM-39(12):1802-1812, December 1991; Parekh et al., “A Generalized Processor Sharing Approach To Flow Control—The Multiple Node Case”,
ACM Transactions on Networking,
2(2):137-150, 1994], and (2) traffic shaping with deadline scheduling, for example [Ferrari et al., “A Scheme For Real-Time Channel Establishment In Wide-Area Networks”,
IEEE Journal on Selected Areas in Communication
, SAC-8(4):368-379, April 1990]. Both of these approaches rely on manipulation of local queues by each router with little or no coordination with other routers. These approaches have inherent limitations when used to transport real-time streams. When traffic shaping without deadline scheduling is configured to operate at high utilization with no loss, the delay and jitter are inversely proportional to the connection bandwidth, which means that low rate connections may experience large delay and jitter inside the network. In traffic shaping with deadline scheduling the delay and jitter are controlled at the expense of possible congestion and loss.
The real-time transport protocol (RTP) [H. Schultzrinne et. al, “RTP: A Transport Protocol for Real-Time Application”s,
IETF Request for Comment RFC
1889, January 1996] is a method for encapsulating time-sensitive data packets and attaching to the data time related information like time stamps and packet sequence number. RTP is currently the accepted method for transporting real-time streams over IP internetworks and packet audio/video telephony based on ITU-T H.323.
One approach to an optical network that uses synchronization was introduced in the synchronous optical hypergraph [Y. Ofek, “The Topology, Algorithms And Analysis Of A Synchronous Optical Hypergraph Architecture”, Ph.D. Dissertation, Electrical Engineering Department, University of Illinois at Urbana,
Report No. UIUCDCS
-
R
-87-1343, May 1987], which also relates to how to integrate packet telephony using synchronization [Y. Ofek, “Integration Of Voice Communication On A Synchronous Optical Hypergraph”,
IEEE INFOCOM'
88, 1988]. In the synchronous optical hypergraph, the forwarding is performed over hyper-edges, which are passive optical stars. In [Li et al., “Pseudo-Isochronous Cell Switching In ATM Networks”,
IEEE INFOCOM'
94, pages 428-437, 1994; Li et al., “Time-Driven Priority: Flow Control For Real-Time Heterogeneous Internetworking”,
IEEE INFOCOM'
96, 1996] the synchronous optical hypergraph idea was applied to networks with an arbitrary topology and with point-to-point links. The two papers [Li et al., “Pseudo-Isochronous Cell Switching In ATM Networks”,
IEEE INFOCOM'
94, pages 428-437, 1994; Li et al., “Time-Driven Priority: Flow Control For Real-Time Heterogeneous Internetworking”,
IEEE INFOCOM'
96, 1996] provide an abstract (high level) description of what is called “RISC-like forwarding”, in which a packet is forwarded, with little if any details, one hop every time frame in a manner similar to the execution of instructions in a Reduced Instruction Set Computer (RISC) machine.
SUMMARY OF THE INVENTION
In accordance with the present invention, a method is disclosed providing virtual pipes that carry real-time traffic over packet switching networks with widely varying link speeds, while guaranteeing end-to-end performance. The method combines the advantages of both circuit and packet switching. It provides for allocation for the exclusive use of predefined connections and for those connections it guarantees loss free transport with low delay and jitter. When predefined connections do not use their allocated resources, other non-reserved data packets can use them without affecting the performance of the predefined connections.
Under the aforementioned prior art methods for providing packet switching services, switches and routers operate asynchronously. The present invention pr
Patel Ajit
Shah Chirag
Sitrick & Sitrick
Synchrodyne Networks, Inc.
LandOfFree
Scheduling with different time intervals does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scheduling with different time intervals, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheduling with different time intervals will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3219347