Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-01-04
2002-11-26
Kizou, Hassan (Department: 2662)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S428000
Reexamination Certificate
active
06487213
ABSTRACT:
§2. BACKGROUND OF THE INVENTION
§2.1 Field of the Invention
In general, the present invention concerns methods and apparatus for arbitrating contention for an output port of a switch (for switching ATM cells for example) or router (for routing TCP/IP packets for example).
§2.2 Related Art
The present invention concerns arbitrating port contention which often occurs when data is directed through a network or internetwork via switches or routers. Before addressing the arbitration techniques of the present invention, a brief description of the emergence of packet switching is provided in §2.2.1 below. Popular data structures used when communicating data are described in §§2.2.1.1.1 and 2.2.1.2.1 below. The basic elements and operations of switches or routers, which are used to direct data through a network or internetwork, are described in §§2.2.1.1.2 and 2.2.1.2.2 below. The idea of prioritizing data communicated over a network or internetwork is introduced in §2.2.2 below. Finally, with all of the foregoing background in mind, the problem of arbitrating port contention in switches and routers, as well as shortcomings of known arbitration techniques, are described in §2.2.3 below.
§2.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. 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 with one another. 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 (2) communications protocols—TCP/IP and ATM—are discussed in §§2.2.1.1 and 2.2.1.2 below.
§2.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 for example, 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 §2.2.1.1.1 below for the reader's convenience.
§2.2.1.1.1 The TCP/IP Protocol 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-level packet
130
. The physical layer converts the network-level packet to radio, electrical, optical (or other) signals sent over the transmission medium at a specified rate with a specified type of modulation.
The TCP header
102
, as illustrated in
FIG. 2
, includes at least twenty (20) octets (i.e., 160 bits). Fields
202
and
204
identify ports at the source and destination systems, respectively, that are using the connection. Values in the
Elallam Ahmed
Kizou Hassan
Pokotylo John C.
Polytechnic University
Straub & Pokotylo
LandOfFree
Methods and apparatus for fairly arbitrating contention for... 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 fairly arbitrating contention for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for fairly arbitrating contention for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2941835