Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-10-14
2004-05-04
Hsu, Alpus H. (Department: 2665)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S399000, C370S409000, C370S413000
Reexamination Certificate
active
06731638
ABSTRACT:
RELATED APPLICATIONS
Not Applicable.
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 packet across a switch with known predefined delay, jitter and loss. Consequently, the end-to-end performance parameters, such as, loss, delay and jitter, have predefined values, which can be with either deterministic or probabilistic guarantees.
Circuit-switched networks, which are still the main carrier of streams of 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 Synchronous Optical NETwork (SONET) or 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, pp. 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 networks 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), pp. 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 Applications”, IETF Request for Comment RFC1889, 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, pp. 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.
Switching architectures for data packet have been extensively studied and developed in the past three decades, see for example [A. G. Fraser, “Early Experiment with Asynchronous Time Division Networks”, IEEE Networks, pp. 12-26, January 1993. Several surveys of packet switching architectures can be found in: [E. W. Zegura, “Architecture for ATM Switching Systems”, IEEE Communications Magazine, February 1993, pages 28-37; A. Pattavina, “Non-blocking Architecture for ATM Switching”, IEEE Communications Magazine, February 1993, pages 37-48; A. R. Jacob, “A Survey of Fast Packet Switches”, Computer Communications Review, January 1990, pages 54-64].
SUMMARY OF THE INVENTION
In accordance with the present invention, the switch scheduling method disclosed is tailored to operate responsive to global common such that the switching delay from input to out put is deterministic and is known in advance. Consequently, such a switch can be employed in the construction of a synchronous virtual pipe (or simply a virtual pipe). Such virtual pipes can carry real-time traffic over packet switching networks while guaranteeing end-to-end performance. The switching and data packet forwarding 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 affe
Hsu Alpus H.
Sitrick & Sitrick
Synchrodyne Networks, Inc.
LandOfFree
Switch scheduling with common time reference does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Switch scheduling with common time reference, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Switch scheduling with common time reference will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3234279