Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-11-04
2002-04-09
Ngo, Ricky (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S395520, C370S395700, C370S412000, C370S429000
Reexamination Certificate
active
06370144
ABSTRACT:
§1. BACKGROUND OF THE INVENTION
§1.1 Field of the Invention
In general, the present invention concerns congestion control and traffic management in networks and inter-networks operating at relatively high data rates and carrying information which may have differing quality of service (or “QoS”) requirements. In particular, the present invention concerns methods and apparatus for fairly servicing queues at an output port of a switch (for switching ATM packets for example) or router (for routing TCP/IP packets for example).
§1.2 Related Art
§1.2.1 The Growth of Network and Internetwork Communications
Communications networks permit remote people or machines to communicate voice or data (also referred to as “traffic” or “network traffic”). These networks continue to evolve to meet new demands placed upon them. Different applications place different demands, often on the same network. In particular, a certain application may require that its traffic be communicated (i) with minimum delay, (ii) at a fast rate, (iii) with maximum reliability, and/or (iv) to minimize communications (service) cost. For example, people would not tolerate much delay in their voice communications during a telephone call. High definition video requires a fast rate, or a high bandwidth, as well as low jitter, or delay variations. However, video communications may be able to tolerate some data corruption or loss to the extent that such losses are imperceptible or not annoying to people. The communications of important data, on the other hand, may tolerate delay, but might not tolerate data loss or corruption. Finally, an application may request that low priority data be communicated at a minimum cost. To the extent that the network traffic of an application does not have “special” requirements, it should be communicated with normal service.
Having introduced the fact that different applications may place different requirements on a communications network, a brief history of communications networks, and the emergence of packet switching, is now presented.
The public switched telephone network (or “PSTN”) was developed to carry voice communications to permit geographically remote people to communicate. Modems then came along, permitting computers to communicate data over the PSTN. Voice and modem communications over the PSTN use “circuit switching”. Circuit switching inherently involves maintaining a continuous real time communication channel at the full channel bandwidth between two points to continuously permit the transport of information throughout the duration of the call. Unfortunately, due to this inherent characteristic of circuit switching, it is inefficient for carrying “bursty” data traffic. Specifically, many services have relatively low information transfer rates—information transfer occurs as periodic bursts. Bursty communications do not require full channel bandwidth at all times during the duration of the call. Thus, when circuit switched connection is used to carry bursty traffic, available communication bandwidth occurring between successive bursts is simply wasted.
Moreover, circuit switching is inflexible because the channel width is always the same. Thus, for example, a wide (e.g., 140 Mbit/second) channel would be used for all transmissions, even those requiring a very narrow bandwidth (e.g., 1 Kbit/second). In an attempt to solve the problem of wasted bandwidth occurring in circuit switching, multi-rate circuit switching was proposed. With multi-rate circuit switching, connections can have a bandwidth of a multiple of a basic channel rate (e.g., 1 Kbit/second). Although multi-rate circuit switching solves the problem of wasted bandwidth for services requiring only a narrow bandwidth, for services requiring a wide bandwidth, a number of multiple basic rate channels must be synchronized. Such synchronization becomes extremely difficult for wide bandwidth services. For example, a 140 Mbit/second channel would require synchronizing 140,000 1 Kbit/second channels. Moreover, multi-rate circuit switching includes the inherent inefficiencies of a circuit switch, discussed above, when bursty data is involved.
Multi-rate circuit switching having multiple “basic rates” has also been proposed. Unfortunately, the switch for multi-rate circuit switching is complex. Furthermore, the channel bandwidths are inflexible to meet new transmission rates. Moreover, much of the bandwidth might be idle when it is needed. Lastly, multiple basic rate circuit switching includes the inherent inefficiencies of a circuit switch, discussed above, when bursty data is involved.
In view of the above described problems with circuit switching, packet switched communications have become prevalent and are expected to be used extensively in the future. Two communications protocols—TCP/IP and ATM—are discussed in §§1.2.1.1 and 1.2.1.2 below.
§1.2.1.1 Internets
In recent decades, and in the past five to ten years in particular, computers have become interconnected by networks by an ever increasing extent; initially, via local area networks (or “LANs”), and more recently via LANs, wide area networks (or “WANs”) and the Internet. In 1969, the Advanced Research Projects Agency (ARPA) of the U.S. Department of Defense (DoD) deployed Arpanet as a way to explore packet-switching technology and protocols that could be used for cooperative, distributed, computing. Early on, Arpanet was used by the TELNET application which permitted a single terminal to work with different types of computers, and by the file transfer protocol (or “FTP”) which permitted different types of computers to transfer files from one another. In the early 1970s', electronic mail became the most popular application which used Arpanet.
This packet switching technology was so successful, the ARPA applied it to tactical radio communications (Packet Radio) and to satellite communications (SATNET). However, since these networks operated in very different communications environments, certain parameters such as maximum packet size, were different in each case. Thus, methods and protocols were developed for “internetworking” these different packet switched networks. This work lead to the transmission control protocol (or “TCP”) and the internet protocol (or “IP”) which became the TCP/IP protocol suite. Although the TCP/IP protocol suite, which is the foundation of the Internet, is known to those skilled in the art, it is briefly described in §1.2.1.1.1 below for the reader's convenience.
§1.2.1.1.1 The TCP/IP Protyocol Stack
The communications task for TCP/IP can be organized into five (5) relatively independent layers—namely, (i) an application layer, (ii) a host-to-host layer, (iii) an Internet layer, (iv) a network access layer, and (v) a physical layer. The physical layer defines the interface between a data transmission device (e.g., a computer) and a transmission medium (e.g., twisted pair copper wires, optical fiber, etc.). It specifies the characteristics of the transmission medium and the nature of the signals, the data rate, etc. The network access layer defines the interface between an end system and the network to which it is attached. It concerns access to, and routing data across, a network. Frame Relay is an example of a network access layer. The internet layer (e.g., IP) defines interfaces between networks and provides routing information across multiple networks. The host-to-host layer (e.g., TCP) concerns assuring the reliability of the communication. Finally, the application layer provides an interface to support various types of end user applications (e.g., the simple mail transfer protocol (or “SMTP”) for e-mail, the file transfer protocol (or “FTP”), etc.).
Basically, each of the layers encapsulates, or converts, data in a high level layer. For example, referring to
FIG. 1
, user data
100
as a byte stream is provided with a TCP header
102
to form a TCP segment
110
. The TCP segment
110
is provided with an IP header
112
to form an IP datagram
120
. The IP datagram
120
is provided with a network header
122
to define a network-l
Chao Hung-Hsiang Jonathan
Jenq Yau-Ren
Ngo Ricky
Pokotylo John C.
Polytechnic University
Straub & Pokotylo
Tran Phuc
LandOfFree
Methods and apparatus for shaping queued packets using a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for shaping queued packets using a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for shaping queued packets using a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2906043