Medium Access Control

Medium Access Control in CAN and IEEE 802.5 token Ring

The size of a broadcast network is measured in terms of the ratio of the network round trip delay to the transmission time of a maximum length packet. If the ratio is small, every station can hear the transmission of every other station immediately after the transmission starts. The network is small when the ratio is small. Circulation control information among the stations in a small network takes small fraction of packet transmission time. The stations can coordinate decisions and actions without incurring significant performance penalty. So, they can carry out a centralized scheduling algorithm in a distributed manner.

Fixed-Priority Scheduling in CAN

Controlled Area Networks are the examples of small networks. CANs are used to connect component of embedded controllers. For example, an automobile control system, whose components control the engine, the brakes, the environment and so on. At the transmission rate of one Mbits per second, the end to end length of a CAN must be no greater than 50 meters. It means, within a fraction of a bit-time after statin starts to transmit, all the stations on the network can hear the transmission. Therefore, the network functionally behaves like a local bus. The output of all the stations are wire-ANDed together by the bus: the bit on the network during a bit-time is a logical 0 if the output of any station is a 0 and a logical 1 only when the outputs of all stations are 1. The MAC protocol for CAN take advantage of this feature. (Liu, 2003, p. 468)

Each message stream transmitted in a network has a unique message ID. Each packet in the stream begins with this ID, with the most significant bit first. A station on the network determines whether to receive a packet based on the ID number of the packet. Finally, a packet contains 1 to 8 bytes of data.

CAN MAC protocol is a CSMA/CD (Carrier-Sense Multiple Access/Collision Detection) protocol. A station with a packet to send waits until it hears that the network is idle and then commences the transmit the ID number of the packet. At the same time the station listens. Whenever it hears a 0 on the network while it is transmitting a 1, it interrupts its own transmission. This way, network contention is resolved in favor of the packet with smallest ID among all contending packets.

So, the packets in each message stream are given a fixed priority that is equal to the ID of the message. The smaller the ID the higher the priority. Packets are transmitted non-preemptively based on their priorities.

Prioritized Access in IEEE 802.5 Token Rings

In an IEEE 802.5 token ring network, packets are transmitted along a circular transmission medium in one direction. By breaking the network, a station transmits a packet and placing on the output link to the network. As the packet circulates around the network, the station identified by the destination address in the packet header copies the packet. When the packet returns to the source station, the station removes the packet from the network.

Polling

Network contention is resolved by a polling mechanism called token passing. For polling, each packet has an 8-bit Access Control field in its header. One of the bits in AC field is called the token bit. A station can determine whether the network is busy or free by examining tokenbit. As a polling packet circulates around the ring, the stations are polled in a round robin manner in the order of their physical locations on the ring. The polling packet is called the free token or simply token when there is no possibility of confusion.

Schedulability Analysis

For scheduling analysis, the following factors can be taken in account.(Liu, 2003, p. 470)

1. Context Switching: A context switching time is equal to the amount of time required to transmit a free token, plus the round-trip delay of the network, which is an upper bound of the time the token takes to reach the station whose outgoing packets has the highest priority among all outgoing packets during the transmission of the latest data packet.
2. Blocking: Since packets are transmitted non-preemptively, we need to take into account the blocking time due to non-preemptivity. A higher priority packet that arrives at a station just after the header of the current data packet passed the station may need to wait for a lower priority packet. The blocking delay caused by this priority inversion must also be taken into account. Hence, the total blocking time is equal to twice the maximum execution time.
3. Limited priority levels: Since the network provides only eight priority levels, schedulability loss should also be take into account

Internet and Resource Reservation Protocol

Resource reservation protocol supports multicast communication among members that may join and leave their multicast groups any time. Resource reservation protocol is separate from routing, admission control, connection establishment and data transmission.

RSVP is a receiver initiated protocol designed to accommodate heterogeneous receivers which may desire different service qualities. An implicit assumption is that not only the group membership may change any time, but also the service quality desired by each individual member may change. Rather that requiring an explicit request to change reservation, resource reservations under RSVP must be removed at frequencies specified by the group members. Both path and reservation states maintained by each router are soft, meaning that the states are deleted if not renewed within specified time intervals.

Another unique feature of RSVP is reservation style. It allows each receiver to specify which source or sources in the multicast group may use the resources reserved on its behalf and to dynamically change this specification if it so desires. This specification is provided to the routers in the form of a filter. A filter names the source whose message streams can use the resources reserved for the receiver.

Issues in Resource Reservation

The resource reservation protocol must deal with the following issues.

1. Multipoint to multipoint communication
2. Heterogeneity of destinations
3. Dynamic multicast group membership
4. Relation to routing and admission control
5. Design objectives

References

Liu, J. W. (2003). Real Time Systems. Pearson Education, Inc. and Dorling Kindersley Publishing Inc.