Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-05-11
2003-10-21
Patel, Ajit (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S392000, C370S351000
Reexamination Certificate
active
06636509
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to internetworking systems and in particular to methods and apparatus for managing traffic flow and quality of service in routers and switches.
2. Description of the Related Art
Internetworking encompasses all facets of communications between and among computer networks. Such communications data flow streams may include voice, video, still images, and data traffic. All have widely varying needs in terms of propagation delay (or latency) during transit through the network. Various systems and devices, both in hardware and in software, have attempted to deal with the plethora of data flow requirements present in modern internetworking systems.
A particular problem in internetworking traffic regulation arises from the variety of traffic sources or flows presented to the router/switching device. Referring to
FIG. 1
, illustrating a high-level schematic view of the operation of a prior art router/switch
100
, a number of input flows
110
are presented to the unit. These flows each consist of multiple packets of data in a variety of sizes and presented at a variety of rates. Flows may also be presented in different protocols, such as the Transmission Control Protocol/Internet Protocol (TCP/IP) and the related User Datagram Protocol (UDP), File Transfer Protocol (FTP), Terminal Emulation Protocol (Telnet), and Hypertext Transfer Protocol (HTTP). Other protocols are found in the literature, such as Merilee Ford, et. al.,
Internetworking Technologies Handbook
(Cisco Press 1997) (hereinafter Ford), incorporated herein by reference in its entirety. The packets are buffered in a buffer pool
120
, which is typically random access memory (RAM). Buffering is accomplished according to the directives of a controller
130
and a buffer manager
140
. The flows are sent to the proper output port
150
by way of a set of output queues
160
and a port scheduler
170
. Controller
130
, buffer manager
140
, and port scheduler
170
are conventionally implemented as one or more high speed microprocessors with associated interface circuitry.
Quality of Service (QoS) is an attribute of the flow in a given data interchange, i.e., a specification placed on the internetworking devices participating in a communications session controlling the timeliness or latency of the communications. Several methods are known in the prior art for configuring QoS in a network, such as the Resource Reservation Protocol (RSVP) described in Chapter 41 of Ford.
One such scheme for ensuring QoS, known as Committed Access Rate (CAR) service, consists of attempting to regulate the traffic within the router or switch connecting multiple networks in the typical internetworking system. Such schemes attempt to provide fair allocation of data throughput capacity (bandwidth) by allocating router buffer and/or queue space according to the type of packets in each flow stream received. A user is, in essence, sold a certain bandwidth, “B.” Flows from that user are not allowed to exceed bandwidth B except when the flows have been consistently less than B for some period of time. Then, and only then, will the switch allow burst traffic (i.e., traffic with bandwidth greater than B) to pass.
Of course, QoS is only useful if there are multiple queues (input and/or output) wherein packets in one queue are given preferential treatment over packets in another queue. In such systems, a method of optimizing queue assignments that allows this differentiated service to be guaranteed (and thus sold to users) is needed.
FIG. 2
illustrates the standard bit configuration for an Internet Protocol packet, including the fields within its header. Flow type, also known as flow classification, information can be found in, for instance, the type of service (TOS) field
210
in the internet protocol (IP) header
200
or in the source address
220
of the received packet. It can also be deduced from the type of packet received, voice being of a higher priority and thus demanding of a larger buffer count than other flows. While dynamic buffer limiting (DBL) is known, current schemes are unable to update their limit values fast enough to keep up with the latest generation of ultra-fast (e.g., Gigabit speed) flows.
As an additional drawback, the use of TOS field
210
is not standardized among internetworking users. Many competing standards, in fact, exist to define how the TOS octet is interpreted.
Examples of competing definitions are found in P. Almquist,
Type of Service in the Internet Protocol Suite
, Internet Request for Comments (RFC) 1349 (July 1992); D. Eastlake III,
Physical Link Security Type of Service
, RFC 1455 (May 1993); and K. Nichols, et al.,
Definition of the Differentiated Services Field
(
DS Field
)
in the IPv
4
and IPv
6
Headers
, RFC 2474 (December 1998), all incorporated herein by reference in their entireties. Thus, neither TOS nor source address is a reliable means of identifying flow type at this time.
Source address
220
is a 32-bit value that describes the source of the IP packet. Since the Internet Protocol is connection-less, i.e., data is transmitted onto the network without first establishing an explicit “connection” between sender and receiver, each packet must contain both the full address of the sender and of the recipient. The content and use of the information contained within IP packet header
200
is described in further detail in K. S. Siyan,
Inside TCP/IP
(New Riders Publishing, 3d ed. 1997) (hereinafter Siyan), incorporated herein by reference in its entirety.
The source address consists of two fields, a network ID and a host ID. The network ID is n bits long (minimum of 8 bits, originally in 8 bit increments, e.g., 8, 16, or 24 bits) and identifies the sending network or “autonomous system” (AS). The autonomous system (AS) is an independently managed network of host computers within an interconnected network of networks. The host ID is (32−n) bits and identifies the particular host computer within the sending AS.
The source address clearly provides an indication of the sender, but, by itself, it does not reveal the priority or required timeliness (i.e., the QoS specified by the sender) for the flow. Indeed, in the modern network, certain flows are actually aggregations of many lower rate flows, each potentially having its own QoS requirement. For example, the Internet backbone carries flows consisting of consolidated traffic from one Internet Service Provider (ISP) to another ISP. Within this aggregated flow are individual packets from multiple discrete flows such as a Voice-over-Internet Protocol (VoIP) call between two users, an HTTP request, and an FTP download. Each packet has its own latency limitation requirement, yet all are within the same ISP-to-ISP aggregated flow. Simply classifying the aggregated flow based on its source address (or AS label) is not sufficient to efficiently allocate switch resources and provide the desired packet level QoS.
A further drawback in the prior art lies in the fact that while all packets within an autonomous system (by definition) use the same TOS field definition, those definitions frequently do not cross AS boundaries. In other words, at the AS-to-AS connection, TOS field meanings are lost.
Thus, in the era of high volume aggregated flows containing packets with numerous divergent QoS requirements, prior art per-flow classification systems are unable to provide the necessary packet-tailored QoS to satisfy users. Such systems are known as “policy” routing schemes for their method of directing resources to flows based on external system administrator decisions on the appropriate flow QoS. Policy routing can define a limited number of custom routing paths for selected packets based on certain criteria (such as source address or physical flow input port). For instance, particular traffic flows, such as VoIP, may be sent over special routes that minimize hop counts and other delay characteristics well-known in the art to ensure high QoS. An example of an element of policy rou
Campbell Stephenson Ascolese LLP
Cisco Technology Inc.
Jain Raj
Patel Ajit
LandOfFree
Hardware TOS remapping based on source autonomous system... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hardware TOS remapping based on source autonomous system..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hardware TOS remapping based on source autonomous system... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3173110