About WTRP
Overview
Wireless networking is a critical enabling technology for Intelligent Transportation Systems (ITS). In recognition of this the Federal Communications Commission recently issued a report and order suggesting co-primary status for ITS Dedicated Short Range Communication Services (DSRC) over 75 MHz of spectrum in the 5.9 GHz band.
Since ITS applications are often delay-sensitive or require fair sharing of the spectrum amongst different users, the ITS DSRC protocols must be designed to provide quality of service (QOS). In an unreliable medium such as wireless, problem of providing quality of service (QOS) at the network layer using queuing and routing techniques is not sufficient. QOS must also be addressed at the data-link layer. The IEEE
802.11 in PCF (Point Coordination Function) mode, the
HiperLAN, and Bluetooth achieve bounded latency by having a central station poll the slave stations. Most academic research has focused on this centralized approach. The centralized approach is suitable for networks where only the last hop is wireless. In the centralized approach, the network is managed centrally from a central station. This is a limitation in wireless networks with ad-hoc topologies.
The Wireless Token Ring Protocol (WTRP) discussed in this paper is a distributed medium access control protocol for ad-hoc networks. The advantages of a distributed medium access control protocol are its robustness against single node failure, and its support for flexible topologies, in which nodes can be partially connected and not all nodes need to have a connection with a master.
WTRP is to be deployed initially in the University of California at Berkeley
PATH Advanced Vehicle Safety Systems Program, the CALTRANS-PATH Demonstration 2002, and the Berkeley Aerobot
project. These projects impose stringent bandwidth, latency, and speed of failure recovery requirements on the medium access protocol. The platoon mode of the automated highway project involves up to 20 nodes in each platoon, and requires that information (approximately 100 bytes per vehicle for speed, acceleration, and coordination maneuvers) be transmitted every 20ms. The failure recovery time for the communication system must be within 40ms.
As in the IEEE 802.4 standards, WTRP is designed to recover from multiple simultaneous failures. One of the biggest challenges that the WTRP overcomes is partial connectivity. To overcome the problem of partial connectivity, management, special tokens, additional fields in the tokens, and new timers are added to the protocol. When a node joins a ring, it is required that the joining node be connected to the prospective predecessor and the successor. The joining node obtains this information by looking up its connectivity table. When a node leaves a ring, the predecessor of the leaving node finds the next available node to close the ring by looking up its connectivity table. Partial connectivity also affects the multiple token resolution protocol (deleting all multiple tokens but one). In a partially connected network, simply dropping the token whenever a station hears another transmission is not sufficient. To delete tokens that a station is unable to hear, we have designed a unique priority assignment scheme for tokens. Stations only accept a token that has greater prioirity than the token the station last accepted. The WTRP also has algorithms for keeping each ring address unique, to enable the operation of multiple rings in proximity.
In the WTRP, the successor and the predecessor fields of each node in the ring define the ring and the transmission order. A station receives the token from its predecessor, transmits data, and passes the token to its successor. Here is an illustration of the token frame.
FC stands for Frame Control and it identifies the type of packet, such as Token, Solicit Successor, Set Predecessor, etc. In addition, the source address (SA), destination addresses (DA), ring address(RA), sequence number(Seq) and generation sequence(GenSeq) number are included in the token frame. The ring address refers to the ring to which the token belongs. The sequence number is initialized to zero and incremented by every station that passes the token. The generation sequence number is initialized to zero and incremented at every rotation of the token by the creator of the token.
The Connectivity manager resident on each node tracks transmissions from its own ring and those from other nearby rings. By monitoring the sequence number of the transmitted tokens, the Connectivity Manager builds an ordered list of stations in its own ring. The Connectivity Table of the manager holds information about its ring
The Ring Owner is the station that has the same MAC address as the ring address. A station can claim to be the ring owner by changing the ring address of the token that is being passed around.
Stations rely on implicit acknowledgements to monitor the success of their token transmissions. An implicit acknowledgement is any packet heard after token transmission that has the same ring address as the station.
Each station resets its IDLE_TIMER whenever it receives an implicit acknowledgement. If the token is lost in the ring, then no implicit acknowledgement will be heard in the ring, and the
IDLE_TIMER will expire. When the IDLE_TIMER expires, the station generates a new token, thereby becoming the owner of the ring.
To resolve multiple tokens (to delete all tokens but one), the concept of priority is used. The generation sequence number and the ring address define the priority of a token. A token with a higher generation sequence number has higher priority. When the generation sequence numbers of tokens are the same, ring addresses of each token are used to break the tie. The priority of a station is the priority of the token that the station accepted or generated. When a station receives a token with a lower priority than itself, it deletes the token and notifies its predecessor without accepting the token. With this scheme, it can be shown that the protocol deletes all multiple tokens in a single token rotation provided no more tokens are being
generated.
The ring recovery mechanism is invoked when the monitoring node decides that its successor is unreachable. In this case, the station tries to recover from the failure by reforming the ring. The strategy taken by the WTRP is to try to reform the ring by excluding as small a number of nodes as possible. Using the Connectivity Manager, the monitoring station is able to quickly find the next connected node in the transmission order. The monitoring station then sends the
SET_PREDECESSOR token to the next connected node to close the ring.
WTRP allows nodes to join a ring dynamically, one at a time, if the token rotation time (sum of token holding times per node, plus overhead such as token transmission times) would not grow unacceptably with the addition of the new node. As illustrated in
Figure , suppose station G wants to join the ring. Let us also say that the admission control manager on station B invites another node to join the ring by sending out a
SOLICIT_SUCCESSOR. The Admission Control Manager waits for the duration of the response window for interested nodes to respond. The response window represents the window of opportunity for a new node to join the ring. The response window is divided into slots of the duration of the
SET_SUCCESSOR transmission time. When a node that wants to join the ring, hears a
SOLICIT_SUCCESSOR token, it picks a random slot and transmits a SET_SUCCESSOR token. When the response window passes, the host node,
can decide among the slot winners. Suppose that wins the contention, then the host node passes the
SET_PREDECESSOR token winner, and winner sends the SET_PREDECESSOR to node next
node, the successor of the host node . The joining process concludes.
Suppose station B wants to leave the ring. First, B waits for the right to
transmit. Upon receipt of the right to transmit, B sends the SET_SUCCESSOR
packet to its predecessor A with the MAC address of its successor, C. If A can
hear C, A tries to connect with C by sending a SET_PREDECESSOR token. If A
cannot hear C, A will find the next connected node, in the transmission order,
and send it the SET_PREDECESSOR token.
we assume that the MAC address of each station is unique the ring address is
also unique. The uniqueness of the address is important, since it allows the
stations to distinguish between messages coming from different rings.
To ensure that the ring owner is present in the ring, when the ring owner leaves
the ring, the successor of the owner claims the ring address and becomes the
ring owner. The protocol deals with the case where the ring owner leaves the
ring without notifying the rest of the stations in the ring as follows. The ring
owner updates the generation sequence number of the token every time it receives
a valid token. If a station receives a token without its generation sequence
number updated, it assumes that the ring owner is unreachable and it elects
itself to be the ring owner.
For detailed description of the protocol please refer to publications.
Product Deliverables
