Multiplex communications – Channel assignment techniques – Arbitration for access to a channel
Reexamination Certificate
1998-06-01
2002-03-12
Chin, Wellington (Department: 2664)
Multiplex communications
Channel assignment techniques
Arbitration for access to a channel
C370S461000, C370S468000
Reexamination Certificate
active
06356560
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to digital data communication systems, and is particularly directed to a new and improved arbitration mechanism for a statistically multiplexed frame relay switching system, which is effective to optimize allocation of a limited bandwidth aggregate data link among access lines that are coupled to respective ports of the frame relay switching system.
BACKGROUND OF THE INVENTION
Frame relay (FR) switching systems currently enjoy widespread success for supplying digital data services—principally in support of local area network (LAN) integration across wide area facilities. Frame relay derives its benefit by multiplexing ‘frames’ of data, or packetized data traffic, from each of a plurality of physical circuits into a common or shared backbone network, so as to reduce overall transport requirements, by creating more efficient use of the available transport bandwidth.
Prior to the advent of frame relay switching systems, LAN integration required the purchase of point-to-point digital data services delivered via individual physical circuits. Among the advantages frame relay provides over point-to-point services are enhanced network reliability and troubleshooting, through redundant and highly manageable switching networks, multiple end-to-end connections via permanent virtual circuits (PVCs) over single physical interfaces, and lower deployment costs that often result in lower consumer fees.
Unfortunately, due to the sporadic nature of data, the efficient utilization of the available bandwidth of such physical interfaces is relatively low, considering the ratio of data transport time (during which the communication circuits are actually sending data over the network) to non-data or idle time (when the circuits are ‘waiting’ for an instruction initiated by the end user). This relatively low efficient utilization is due principally to a common attribute that is shared by a significant number of typical data networking applications (such as e-mail, web-browsing, terminal input, automatic teller machines, and credit card verification devices); much of the data traffic they generate is in response to some human intervention.
As a non-limiting example, when using a web browser, an end customer may download a magazine article from a web site; the user will then probably spend some period of time reading or at least skimming the article, before ‘surfing’ for something else. During the time interval that the user is reading the article, the available bandwidth of the data connection is essentially wasted, since no data is being transmitted. While this low utilization efficiency may not be significant in terms of a single dial-up customer, when multiplied by thousands of users, it results in a large number of bandwidth resources being utilized at far less than capacity. This low utilization of available bandwidth results from the necessity of back-hauling services from the communication service supplier (e.g., an internet service provider (ISP)) to the switching backbone.
In a typical implementation, rather than being dispersed throughout the network, the switching backbone is confined to a very limited geographic area, requiring significant back-haul support. In addition, in stark contrast to the widespread availability of central office voice switches, the number of available data switches is relatively small. Also, due to the nature of physical interface design, a frame relay switch is often not necessarily employed in a manner that makes full use of its frame processing functionality. By accessing the frame relay switch through point-to-point facilities, both data transport time and idle time are presented to the switch interface. The frame relay switch then becomes limited at the point of its physical port access, often mandating the purchase and installation of additional frame relay switches and line cards.
In order to better utilize frame relay switch capability, as well as increase the utilization of back-haul transport bandwidth, it is desirable to efficiently extend frame multiplexing to central offices, remote terminals (RTs) and customer premises equipment (CPE) environments in a manner that address current deployment schemes. For this purpose, it has been proposed to implement frame relay switching networks in an architecture of the type diagrammatically shown in FIG.
1
.
In this architecture, a plurality of frame relay channel units (frameports)
11
terminate a large number of access lines
13
from associated CPEs
15
, and are coupled to an aggregate data link
21
from the network
10
. The aggregate data link has a data transport capacity that is considerably less than the cumulative data capacity of all of the access lines
13
. Integrated into this architecture is a transport access mechanism that statistically multiplexes data from the various CPEs
15
into a single data stream for transport over the aggregate data link
21
. The use of statistically multiplexing serves to reduce the back-hauling of circuits to the data switch, thereby more efficiently utilizing aggregate data transport resources, since the data is multiplexed at the point of access (the respective frame relay channel units
11
), rather than at the switch.
In order to provide an orderly and efficient allocation of the limited bandwidth of the aggregate link
21
to each access line
13
requesting service, yet without allowing any individual access line to tie up the aggregate data link during periods of inactivity or congestion, the statistical multiplexing of data from the access lines to the aggregate data link is based upon a prescribed opportunity-to-transmit arbitration mechanism, that is distributed among all users of the system, so that the state of the system is effectively shared with each access line.
For this purpose, each frame relay channel unit
11
is coupled to a common (wire-ORed) arbitration link
12
, that allows each channel unit to simultaneously share arbitration information, through which ‘ownership’ of the aggregate data link
21
is allocated in accordance with a specified ‘right to transmit’ rule set.
SUMMARY OF THE INVENTION
In accordance with the present invention, there is provided a new and improved arbitration mechanism for controlling the manner in which data from a plurality of access lines, the cumulative bandwidth of which far exceeds that of the aggregate data link, is statistically multiplexed through a frame relay switching system of the type described above, by calculating for each data line an arbitration value based upon a combination of parameters, including queuing delay and information customized for the particular configuration and traffic rate of that line.
As will be described, the arbitration mechanism of the present invention enables user devices to readily interface with each other, in order to determine which device should have access to the aggregate data link, regardless of the degree of traffic congestion. The arbitration mechanism of the invention is able to accommodate periods of aggregate link congestion in a fair, orderly and predictable manner, that ensures that the oldest data packet awaiting transmission will not be excluded from gaining access to the aggregate data link to the benefit of initially higher priority class of service lines.
For this purpose, the control processor of each frame relay channel unit executes a statistical multiplexing arbitration routine, which calculates a respective arbitration value that forms part of the contents of a composite arbitration code presented to and readable by each frame relay channel unit, via a common physical medium (wire-ORed arbitration bus) during a respective arbitration cycle. The use of a common physical arbitration medium allows each participating channel unit to simultaneously share its arbitration code with all other channel units. Since arbitration cycles will occur: at a rate that is directly proportional to the flow of data into the network, they are not periodic and are asynchronous to other system events.
The channel units op
Schofield Wade S.
Venters W. Stuart
Williams Philip David
Adtran Inc.
Pham Brenda H.
LandOfFree
Arbitration mechanism for statistically multiplexed frame... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Arbitration mechanism for statistically multiplexed frame..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arbitration mechanism for statistically multiplexed frame... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2844476