Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-05-01
2001-10-16
Chin, Wellington (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S389000, C370S235000, C725S097000
Reexamination Certificate
active
06304578
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to routing of data packets over a network and, in particular, to methods and apparatuses for improved packet routing and queuing at the headend of a shared data channel that services a number of users attached to the same shared data channel.
2. Description of the Related Art
Data packet communication on the Internet is dominated by traffic transported using the transport communication protocol/Internet protocol (TCP/IP) suite of protocols. The Internet protocol (IP) header of these packets contains information related to recipient and sender addresses and ports, packet size, and protocol encapsulated in the IP packet, such as transport communication protocol (TCP), user datagram protocol (UDP), or Internet control message protocol (ICMP). A data packet (“packet”) is a finite set of data and associated control bits of a standard maximum size, having a predefined protocol and organization.
When a user (or client) requests a web page containing embedded images, there will then be a number of TCP/IP sessions, in which information is transmitted between the web page server and the client server using TCP/IP. The number of TCP/IP sessions is equal to one more than the embedded image total, since an initial request is required to download the HyperText Markup Language (HTML) file describing the page and its contents. Each of these interactions consists of three stages: connection establishment, data transfer, and connection termination. A connection is established using a “three way handshake,” with a request from client to server, a response from the server, and an acknowledgment of the response. During this stage, the maximum packet size is agreed on. A document request then goes to the server, and the server responds. Each packet from server to client or client to server is acknowledged, either in its own packet, or “piggybacked” in a data packet. The closing of the connection requires an exchange of FIN commands, each one being acknowledged by the other end. A FIN command (for “finished”) is a flag set in the packet header indicating that the sender is finished sending data.
Thus, in the first exchange, the client requests the HTML document describing the page. Upon receipt of this document, the web browser parses the document, and then initiates a series of connections for each of the embedded images (or any other type of file which may be part of the page). In typical current usage, all of these exchanges occur under software control; the user has only clicked on a hypertext reference or entered a uniform resource locator (URL). As a result, these sessions will be set up and torn down faster than if they were user-initiated. Only the data packets from the server to the client that contain the document and the images are likely to be large; any packets other than data packets, e.g. control packets, will be relatively small, consisting of little more than the TCP/IP header and sometimes a small amount of control data. Further background information on TCP and IP may be found in W. R. Stevens,
TCP/IP Illustrated,
Vol. 1 (Addison-Wesley, 1994).
When transmitting data packets over a network such as the Internet, a last headend (or central office, point of presence, corporate gateway, or the like) is typically reached, which services a number of users on a data channel, with a headend router. Such data channels having a single headend serving a number of users are sometimes referred to as shared data channels. A headend router is at the “headend” of a given shared channel and serves as the communications interface with external networks. In this capacity, a headend router routes data packets received to the appropriate user and also prioritizes and schedules data packets for routing to users. After a data packet is received by the headend, the headend router then passes the data onto the appropriate user on the shared channel. A bottleneck can occur at this point if the available bandwidth is insufficient to satisfy the demand (e.g., transmission bandwidth on the channel itself or transmission and/or processing bandwidth of the router or headend), resulting in queuing of “downstream” packets (i.e., packets destined for a user of the shared channel serviced by the headend).
For example, a plurality of users may be attached to a given headend, which itself is coupled to the Internet. One of the users may request a HyperText Markup Language (HTML) document (i.e., web page) from a web server coupled to the Internet. This document may be routed through the Internet in the form of packets, and ultimately delivered to the user's own headend. The headend then typically immediately routes the packets to the recipient/user with the headend router, if possible, or queues them in a buffer (typically, a first-in, first out (FIFO) buffer) if other packets are currently occupying the shared channel.
The two parameters that characterize this queuing of packets intended for given recipients are latency (the time between document request and the beginning of receipt) and throughput (the rate at which the document arrives once the first packet of the document has been received). As the buffer feeding the shared channel gets more full, it takes longer for a packet to be processed, and if either the buffer overflows or the packet is not received by a user before being timed out, packets need to be retransmitted. As a result, effective throughput will drop below what the remote server and the Internet are capable of delivering. Further discussion of queuing and related issues may be found in L. Kleinrock,
Queuing Systems, Vol. II: Computer Applications
(John Wiley & Sons, 1976); N. K. Jaiswal,
Priority Queues
(Academic Press, 1968); and V. N. Padmanabhan & J. C. Mogul,
Improving HTTP Latency
(presented at the 2
nd
World Wide Web Conference, Chicago, 1994).
Thus, in many networks such as the currently-configured world-wide web (WWW) of the Internet, a user is faced by highly variable latency and throughput, due to the queuing behavior caused by the unavoidable bandwidth limitations of such networks and distribution systems. These problems are manifest even as higher rate services such as cable modems and high speed digital subscriber loops are being introduced. For example, after a user requests a document or other data (for example, by clicking on the URL or hyperlink on a given web page using a web browser), it may take a first time delay before the connection to the web server sending the requested document is acknowledged. After the connection is acknowledged (typically by an appropriate message being displayed on the user's browser), a second time delay elapses before the first packets of data for the document begin to be delivered to the user and thus displayed. Once document delivery begins and the document begins to display, it may take some time before the entire document and its contents are painted on the screen, and this may occur in jerky, choppy, stop-and-go fashion, which may be annoying and frustrating to users who see part of a picture, for example, but are unable to see the complete picture for a substantial length of time, due to long periods between data bursts.
It may be difficult to justify the premium price to be charged to some users, if users are still dissatisfied with this highly variable latency and throughput at certain high-traffic times. For this and other reasons, therefore, it is desirable to improve the perceived performance.
SUMMARY
In the present invention, the data packet queuing and routing behavior of the headend of a shared data channel is modified to improve document delivery performance perceived by users of the shared data channel. Although transmission bandwidth constraints may make improvements of absolute performance impractical, improvements in perceived performance are advantageous since, for example, such improvements can improve comfort and ease of use of a given service, reduce frustration and dissatisfaction, and the like. The term “headend” is used he
Chin Wellington
Duane Morris & Heckscher LLP
Lucent Technologies - Inc.
Nguyen Steven
LandOfFree
Packet routing and queuing at the headend of shared data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Packet routing and queuing at the headend of shared data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packet routing and queuing at the headend of shared data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2571889