Multiplex communications – Pathfinding or routing – Combined circuit switching and packet switching
Reexamination Certificate
1999-09-28
2004-05-18
Ton, Dang (Department: 2666)
Multiplex communications
Pathfinding or routing
Combined circuit switching and packet switching
C370S395200, C370S395310, C370S401000, C370S412000
Reexamination Certificate
active
06738371
ABSTRACT:
FIELD OF INVENTION
The present invention pertains generally to the field of packet data networks and, more particularly, to system architectures and methods for regulating and managing the flow of data packets in a packet data router.
BACKGROUND
In a typical packet data router, packets originating from various source locations are received via a plurality of communication interfaces. Each packet contains routing information, such as a destination address, which is associated with a respective communication interface of the router, e.g., by a routing table or packet forwarding protocol. The router reads the routing information of each received packet and, if it recognizes the information, forwards the packet to the appropriate communication interface for further transmission to its destination. Packets without known destination address or forwarding protocol information are typically dropped.
Due to normal ebbs and flows in packet data traffic patterns and volume, a packet data router may be unable to immediately route newly received packets to respective designated communication interfaces. In particular, packet data traffic tends to have bursts of high activity, which is followed by lulls. Thus, a packet data router may be characterized as having a sustained data rate and a burst data rate. When receiving a burst of packet traffic, the router will temporarily store the received packets in an associated memory until t has the processing capacity available to process and forward the packets to their respective outgoing communication interface. When the sustained or burst data rates of a router are exceeded for a certain period of time, it is inevitable that further incoming packets will be dropped. Of course, while sometimes unavoidable, dropping unprocessed packets is undesirable because the source will then retransmit the dropped packet as part of its recovery procedure, which tends to prolong the congested state of the packet router and cause further unprocessed packets to be dropped.
Packet data network users often share either a single router, or router system, from a service provider. Multiple different internet users, for example, may connect via respective data modems or primary rate interface (“PRI”) lines to a single internet protocol (“IP”) router, or IP router system, operated by an internet service provider (“ISP”). These end users may be single customers themselves, or there may be multiple (e.g., networked) users combined as a single customer account by the ISP. Each customer account may be allocated a respective level of service priority and packet throughput bandwidth by the ISP, depending on the type and level of service connectivity that is contracted for.
For purposes of clarification, as referred to herein, a “router” is defined as a physical (as opposed to logical) entity having a defined number of physical communication interfaces (e.g., modems) under the control of one or more processors collectively executing a single control function. Typically, a single physical router operates under a single routing domain—i.e., wherein a packet received on any communication interface may be forwarded only to the same, or any other communication interface of the router. As referred to herein, a “router system” is defined as two or more independent routers, with an external controller for selectively directing common (incoming) packet data traffic to respective routers within the system.
It is known to implement within a single router one or more virtual router instances (“VRIs”). Each VRI has its own subset of communication interfaces, or logical circuits on a shared communication interface, and its own routing domain, but still under the control of a common control function with the other packet traffic handled by the router. In particular, a VRI exists as a collection of processes performed by the router, which correspond roughly to the layers in the TCP/IP protocol model. For example, a private network can be configured as a VRI, so that packet data may only be exchanged between end users on the same network. It has also been proposed to have a single VRI span multiple routers in a router system. For example, one suggested implementation is to have a dedicated interface link bridging respective communication interfaces of multiple routers having a common VRI.
Because of varying and often unpredictable growth rates, as well as other economic factors, a packet router, or packet router system, will not necessarily have the processing or memory capacity to simultaneously provide the contracted for bandwidth allocation for every user or VRI it services. Further, various users will connect to the IP router at different, often unpredictable, times and with varying rates and bandwidth needs.
An IP router is typically controlled with a real time operating system (“RTOS”), which allows multiple processes of different priorities to co-exist under the control of a common control function (e.g., within a single central processing unit). For example, the RTOS may have sensors that provide feedback information regarding current usage characteristics for a given user, which is used to adjust the RTOS operating parameters in response to changes in demand. Common applications for the RTOS are process control, motion control and, in certain applications, command and control.
The problem is that these operating systems often fail to effectively accommodate the different priority and bandwidth requirements contracted for by the end user customers of the ISP. In a motion control system, for example, the flow of information from sensors is into the system, and the flow of control signals is out of the system. There may be a lot of sensors, and there may be a lot of subsystems being controlled, but the input information does not circulate through the system and become the output. This has the effect of making the inherent control feature of the RTOS process/task priority ineffectual for controlling the system.
A typical IP router is a “packet driven” system. The more data packet it receives, the greater the load, and that load traverses the whole system such that the input is (for all practical purposes) the output. Thus, users whose connection to the router is handling the most packets will tend to monopolize the system resources.
For example, consider a router that is divided into two different VRIs, with each VRI having roughly the same number of end users and paying an ISP for the same quality of service (“QOS”), including identical priority and bandwidth requirements. Thus, the router should be able to provide the end users of each VRI with the same number of bits-per-second (“BPS”) system throughput at any given time. Suppose, however, that the router processing capability is barely adequate to handle the peak load of even one of the VRIs without dropping unprocessed packets. If users of the first VRI have, in effect, tied up the router throughput processing capabilities, the users of the second VRI will not receive the service priority and bandwidth they are otherwise entitled to.
Thus, there is a need for methods and system architectures for more fairly regulating the processing of data packets through a packet data router, or router system, whereby the quality of service is balanced for each user and/or VRI, and wherein the system is kept stable, even when heavy loads occur.
SUMMARY OF THE INVENTION
In accordance with a first aspect of the invention, a method is provided for controlling the processing of data packets in a packet data router by dynamically adjusting the rate at which packets held in a respective ingress data queue are processed based on current operating conditions of the router.
In a preferred embodiment, the ingress data queue has a data queue head structure including a packets-to-be-processed field and a sustained-data-rate field. The packets-to-be-processed field stores a value indicating a number of packets held in the ingress data queue that are to be processed by the router during a given processing interval. In this manner, the packet flow rate of the in
Ericsson Inc.
Mehra Inder Pal
Ton Dang
LandOfFree
Ingress data queue management in a packet data router does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Ingress data queue management in a packet data router, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ingress data queue management in a packet data router will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3225878