Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-08-11
2003-12-02
Jung, Min (Department: 2663)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S395200, C370S329000, C370S462000
Reexamination Certificate
active
06658007
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the field of telecommunication networks and packet switching and, in particular, to medium access control protocols and transmission scheduling in shared media point to multipoint cell-switched networks.
BACKGROUND
As the concept of asynchronous transfer mode (ATM) gains wide acceptance, network designers are facing the issue known as “the last mile problem”. There are cost effective ways to switch user information locally, i.e. LAN and voice switches, just as there are cost-effective ways to interconnect cities, i.e. fiber optics cables carrying synchronous digital hierarchy (SDH) traffic, which can serve as trunks for ATM switches. The “last mile” is the region between the user and the wide area network.
There are two classes of last mile access: dedicated links and shared media. Dedicated links include the copper twisted pairs (possibly with ADSL enhancement), some coax installations and point to point radios. Shared media include point to multipoint radio, coax, and some fiber optics solutions. Shared media has two main advantages: first, cost reduction at the head-end by serving many customers with a single unit; and second, the flexibility of dynamically allocating the shared capacity among the users based on instantaneous needs.
However, shared media poses several issues, such as how to maintain integrity if one user fails and floods the media with interfering signals and how to share the media fairly among the users. In particular, there is an issue of how to guarantee each user a quality of service (QoS) performance for each particular service, such as constant bit rate circuit emulation services (CBR-CES) and available bit rate (ABR).
These issues have been partially addressed by a family of techniques that include the following:
1. A base station (BS) controls the operation of the subscriber terminals (STs).
2. Transmissions on the medium can be made from the BS to STs (downstream) or from ST to the BS (upstream) but not from ST to ST.
3. The downstream transmission is a broadcast to all users, and the destination ST is specified by a media access control (MAC) address.
4. The upstream transmission is moderated by the BS, and the BS specifies which ST will transmit at each given transmission opportunity (or “slot”).
5. All user-generated traffic is transmitted based on grants from the BS, and no data is transmitted in a contention slot, such as slotted ALOHA.
6. Contention slots or polling are used for bandwidth reservation.
The various techniques differ in the way they support multiple services in the upstream direction. For example, a customary technique is to define a time division multiplex (TDM) table such that each ST is allocated a few slots within the TDM table based on the user's traffic load. The TDM table includes contention slots for bandwidth requests and one-user slots for data transfer. However, the customary technique is too slow to respond to momentary bursts of traffic of specific users.
An alternative technique disclosed in application Ser. No. 08/708,593 eliminates the TDM table at the ST and instead maintains the timing information at the BS for all users. In accordance with the alternative technique, the BS calculates the time intervals of CBR virtual circuits (VC) and queues a grant for each VC when its time has matured. Non-time-critical services such as ATM nrt-VBR send requests via contention slots or attached to any upstream cell MAC overhead. The requests carry a summary of the total buffer occupancy in the ST (excluding CBR), and the ST calculates an urgency figure for the buffer's status. The requests are prioritized by the BS. Once the BS decides which ST gets a grant, the grant is sent without specifying which VC within an ST can use the grant. Thus, the alternative technique provides non-directed grants.
Another example of scheduling ATM flow over a wireless network is discussed in the paper entitled “Guarantee Quality of Service Wireless Access ATM Networks” by C-S. Chang, K-C. Chen, M-Y You and J-F. Chang in IEEE J. Sel. Areas Com. Vol. 15. No. 1, January 1997, p. 106. The paper provides performance analysis of a wireless ATM network in which CBR transmission “tokens” are generated periodically and have higher priority than non-CBR traffic. Among the CBR tokens, the one selected for current transmission is the one with the highest static priority. This approach allows a bound to be calculated on the worst case delay of each VC. However, this approach lacks fairness, because a VC of similar quality objectives but lower priority will get a lower grade of service.
SUMMARY OF THE INVENTION
In accordance with the present invention, requests and grants are directed, i.e. specified per VC. Accordingly, in one embodiment of the present invention, a per-VC scheduler is provided, and MAC layer protocol formats for implementing requests and grants are also provided. A point to multipoint microwave ATM network and other shared media with mechanisms to request and grant bandwidth in the shared media are also disclosed.
In one embodiment, an ATM access network includes subscriber terminals (STs) located in several buildings in a section of a city and a base station located within a few kilometers of the STs. Each ST is connected to a plurality of user interfaces such as an ISDN basic rate interface or a 10BaseT Ethernet. The user traffic is converted to ATM traffic for upstream transmission. ATM traffic is also received from the BS and converted to the user interface format. After an ST has completed an admission process that sets the right carrier frequency, transmission power and transmission delay, the ST is ready to provide ATM services.
ATM traffic flow scheduling in accordance with one embodiment of the present invention includes the following:
1. Requests and grants that include virtual circuit (VC) information, in which a VC represents a virtual path identifier/virtual channel identifier (VPI/VCI) of an ATM cell's flow.
2. A periodical request-less per VC scheduler residing at the BS, called a “virtual framer”.
3. A request-based per VC scheduler residing at the BS, called a “virtual shaper”.
In one embodiment, if the service of a particular VC is constant bit rate (CBR) or otherwise requires critical real time performance, then a BS scheduler called a “virtual framer” is invoked to provide periodical request-less grants to the VC. Specifically, the grants specify which ST and which VC within the ST can use the grant to transmit one ATM cell, and the grants are transmitted as MAC overhead in the downstream direction.
More specifically, the virtual framer resides at the BS and includes a table of traffic records that define the source ST and the cell transmission interval. A microcontroller writes these records at the connection set up time. The microcontroller also generates a request on behalf of the ST to send one grant. The request is queued in the virtual framer, and the request is then processed. The virtual framer checks a traffic record, calculates the next compliant time (NCT), which for CBR traffic is simply the last calculated transmission time plus the cell's transmission interval. A grant is generated with the NCT as a priority descriptor. The grant enters a sorted priority queue in which it waits until the grant has “matured” (i.e., until the current time has met or exceeded the NCT). The matured grant is placed in a high priority queue of matured grants, and the matured grant is sent to the ST via the MAC overhead when it reaches the head of the line. Also, when a grant has matured, a new request is generated for the VC, and the new request is placed in the input queue of the virtual framer to keep the periodical scheduling process active. The traffic record includes the NCT variable which is compared with the current time. Because the time variable grows indefinitely, a finite binary number will overflow and indicate an earlier time than it should. A numerical roll-over technique similar to Gray coding is used so that as long as the cell transmission int
Aaronson Itai
Ben-Efraim Gideon
Pasternak Eliezer
Bingham & McCutchen LLP
Jung Min
Marino Fabio E.
Ming Erin C.
Netro Corporation
LandOfFree
Grant processing in wireless ATM networks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Grant processing in wireless ATM networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Grant processing in wireless ATM networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3182044