Electrical computers and digital processing systems: multicomput – Computer-to-computer session/connection establishing – Network resources access controlling
Reexamination Certificate
1998-11-03
2001-02-27
Maung, Zarni (Department: 2758)
Electrical computers and digital processing systems: multicomput
Computer-to-computer session/connection establishing
Network resources access controlling
C709S200000, C709S234000, C370S395430, C370S397000
Reexamination Certificate
active
06195699
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to real-time resource scheduling, more specifically, to a method and apparatus for the real-time scheduling of a shared resource in an information system such as in digital communications between terminals of a communications network.
2. The Prior Art
When two computers wish to communicate with each other, they do so via a communications network. Networks are composed of computers and other terminal devices, such as printers, (collectively, computers) that are interconnected by electrical or optical cables. The capacity of a cable, also called its bandwidth, is measured in bits per second. The sum of the bit rates over all connections supported at one time by a cable cannot exceed its capacity.
Many networks are networks within networks, that is, larger networks composed of smaller networks connected together. For example, a company may have a local area network (LAN) in one of its offices that ties together all of the computers in that office. It then has a wide area network (WAN) that ties together the local networks of all of its offices. The company WAN may then be connected to a larger WAN, such as the Internet, a global network of thousands of smaller networks and computers. Generally, a network is connected to another network at one point, the gateway, where a hardware device, the interworking unit (IWU), acts as a translator between the different communications protocols and bit rates of the connected networks.
In general, information transferred from one computer to another over a network is not sent continuously. The information is broken up into segments, called packets, each of which is prefixed with a header and sent. The header may contain various information, such as the address of the source computer, the address of the destination computer, and the position of the packet in the totality of information sent from the source to the destination. The later is necessary when it cannot be assumed that all the packets will reach the destination by the same route, implying that the packets may arrive at the destination in a different order than they are sent. In the typical network, the amount of time that it takes to transmit each packet is the packet transmission interval, and is determined by dividing the length of the packet, in bits, by the bit rate of the network.
With the proliferation in the number and power of computers and the desire for computers to communicate at increasingly higher speeds, network bit rates must continue to increase to keep up with the demand for their services. Some WAN lines currently run at bit rates of up to 2.4 Gb/s using asynchronous transmission mode (ATM) standards, with higher rates anticipated. In an ATM system, each information packet is sent as a series of fixed-size cells. At 2.4 Gb/s, a 53-octet ATM cell has a cell interval of (53 octets*8 bits/octet)/2.4 Gb/s=176 nanoseconds (ns).
When it is desired to send information from a source system to a destination system, a virtual connection (VC) is set up. A VC is a logical connection between the systems. The physical transmission path (which may include electrical wires, optical fibers, and intervening computers) will often have segments that are shared by several VC's. Of course, the physical medium used for each segment must provide sufficient bandwidth to meet the requirements of all VC's set up through it.
In a segment of a transmission path, packets can be transferred synchronously or asynchronously. In synchronous transfer mode (STM), data is transferred within equal time periods, or frames, which are themselves composed of time slots. The number of time slots in each frame typically is the same as the maximum number of VC's. A VC that passes through an STM segment is assigned one slot within the frame. Consequently, all channels using this transmission segment have the same fixed bandwidth, regardless of actual need. If the fixed bandwidth is more than is necessary for the VC, some of the bandwidth is wasted. Conversely, if the fixed bandwidth is less than is necessary, some information may be lost.
In asynchronous transfer mode (ATM), there are no frames. Packets are allocated time slots when needed. Consequently, each VC only uses the bandwidth that it needs. When a system wishes to send information over an ATM network, it sends a request to the network controller for a VC that will run at a specified bandwidth. The VC is allocated and the interval of time between cells necessary to meet the bandwidth requirement, the rate period, is determined. Then the cells are sent one at a time during an access interval, called a cell interval in communications systems, separated by the rate period. The network controller must determine which cell to assign to each cell interval. Because the number and assignments of VC's change dynamically, it is not generally possible to make cell interval assignments in advance. Thus, each cell interval assignment must be made in real time during the previous cell interval, which means that the transmitting unit only has the amount of time in a cell interval (176 ns in the 2.4 Gb/s example above) to make the next assignment.
In present day ATM transmission equipment, the scheduling of transmission of ATM cells is typically implemented using a scheduling table that contains an arbitrary number of entries. Each entry in the table specifies a particular virtual channel (VC) and each VC may appear in many entries of the table. Sometimes, the table has a hierarchical structure. The scheduler cycles through the table repeatedly, processing one entry every cell interval. This method is simple, but has several problems, including the difficulty of maintaining the table as VC's become active or inactive, and the limited accuracy of the channel period due to the finite size of the table.
SUMMARY OF THE INVENTION
An object of the present invention is to provide an apparatus for determining in real time which cell to assign to each cell interval in an asynchronous transfer mode communications network that serves a number of virtual channels.
Another object is to provide such an apparatus that can be reconfigured in real time to accommodate various parameters of an asynchronous transfer mode communications network, including dynamic activation and deactivation of virtual channels and changing rate periods of virtual channels.
The real-time scheduler of the present invention may be used to schedule service of multiple periodic requests for access to a shared resource. An important example is determining when each virtual channel of an asynchronous transfer mode communications system can use the single transmission line.
The real-time scheduler includes a set of inputs, a scheduling table, an arithmetic unit (ALU), a smallest value logic block (SVL), and a comparator. The significant inputs are the channel periods and the channel active indicators. The channel period is the ideal time between which cells of a single channel should be sent and the channel active indicators indicate whether a channel is currently active in systems that have dynamically activated and deactivated channels.
The scheduling table stores an ideal value for each channel, which is the earliest time that the next cell should be sent and is based on the channel period. The scheduling table is partitioned into a fine table, which contains the portion of the channel value that is in units of cell intervals, and a coarse table, which contains the portion of the channel value that is in units of scheduling periods, where a scheduling period is defined as the maximum number of cell intervals that can be represented by a fine value.
Two processes take place in parallel during each scheduling period, the coarse process and the fine process. In general, the coarse process uses the ALU to decrement all non-zero coarse values. A post-decrement coarse value of ‘0’ indicates that the ideal time for the associated channel falls in the next scheduling period.
During the fine process, the
Acorn Networks, Inc.
Maung Zarni
Morse, Altman & Martin
Tran Philip B.
LandOfFree
Real-time scheduler method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Real-time scheduler method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Real-time scheduler method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2605524