Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-03-28
2004-08-17
Hsu, Alpus H. (Department: 2665)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S412000, C370S429000
Reexamination Certificate
active
06778536
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates generally to a method and apparatus for switching of data packets in a communications network in a timely manner while providing low switching complexity and performance guarantees.
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 almost 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 almost 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] 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 (Asynchronous Transfer Mode) 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 defined for ATM include constant bit rate (CBR), variable bit rate (VBR) and available bit rate (ABR).
The methods for providing different services with packet switching fall under the general title of Quality of Service (QoS). The latest effort in QoS provision over the Internet is carried on by the Differentiated Services (DiffServ) Working Group of the Internet Engineering Task Force (IETF). DiffServ is working on providing QoS on a per-class basis, i.e., each switch provides a different service to packets belonging to different classes. The class to which a packet belongs is identified by a field in the IP packet's header. The DiffServ Working Group has re-defined the usage of the field originally called Type Of Service and has re-named the field DS (Differentiated Services) byte [K. Nichols, S. Blake, F. Baker, D. Black, “Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers,” IETF Request for Comment RFC 2474, December 1998].
DiffServ relies on (i) a relatively small set of generic Per Hop Behavior (PHB), which define ways for individual switches to perform packet forwarding, and (ii) access control at the boundary of the network. A switch is configured to apply a specific PHB to each service class (i.e., switches are configured with a mapping between DS field value and corresponding PHB). A number of transport services can be built on those PHBs, including premium service, which is expected to deliver packets end-to-end within short delay and with low loss. 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.
Q-STM (Quasi-Synchronous Transfer Mode) [N. Kamiyama, C. Ohta, H. Tode, M. Yamamoto, H. Okada, “Quasi-STM Transmission Method Based on ATM Network,” IEEE GLOBECOM'94, 1994, pages 1808-1814] uses a frame/subframe/slot structure to regulate the forwarding of ATM cells through the network. However, the authors do not suggest or mention the deployment of a common time reference, or the capability to transport variable size data packet, or the ability to combine “best effort” and variable bit rate (VBR) traffic types.
In U.S. Pat. No. 5,418,779 Yemini et al. disclose a switched network architecture with a time reference. The time reference is used in order to determine the time in which multiplicity of nodes can transmit simultaneously over one predefined routing tree to one destination. At every time instance the multiplicity of nodes are transmitting to a different single destination node. However, the patent does not teach or suggest the synchronization requirements among nodes, or the means in which it can be provided, or the method in which it can be used.
In the context of the Highball Project [D. L. Mills, C. G. Boncelet, J. G. Elias, P. A. Schragger, A. W. Jackson, A. Thyagarajan, “Final Report on the Highball Project,” Technical Report 95-4-1, University of Delaware, April 1995] a network intended for a moderate number of users (10-100) was developed, deployed, and tested. Nodes are synchronized and transmission resources are reserved to flows so that packets always find output links available on every node traversed. No queuing is performed inside nodes; all queuing is done at the periphery of the network. This requires higher accuracy in the synchronization among nodes and affects the robustness of the system.
Architectures for data packet switching 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 fabric architectures can be found in: [R. Y. Awdeh, H. T. Mouftah, “Survey of ATM Switch Architectures,” Computer Networks and ISDN Systems, No. 27, 1995, pages 1567-1613; 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].
Circuit switches exclusively use time for routing. A time period is divided into smaller t
Baldi Mario
Ofek Yoram
Sitrick & Sitrick
Synchrodyne Networks, Inc.
LandOfFree
Combined wavelength division multiplexing, time division... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Combined wavelength division multiplexing, time division..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combined wavelength division multiplexing, time division... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3303852