ADC Home > Reference Library > Technical Notes > Legacy Documents > Networking >

Legacy Documentclose button

Important: This document is part of the Legacy section of the ADC Reference Library. This information should not be used for new development.

Current information on this Reference Library topic can be found here:

Routes From the Source

CONTENTS

This Technical Note discusses source routing and its possible implementation in token ring link layers.

[Jan 01 1992]






Introduction

"AppleTalk," in the words of Gursharan Sidhu, "is a network system." As such, it provides for multiple types of media and data links, and token ring is one such data link.

Source routing refers to a process on token ring networks where the source of a packet indicates, to any bridges between the source and the destination, the route a packet must take to get from the source to the destination. The destination also uses this same route to transmit the response packet back to the proper place. The presence of routing information is indicated by a 1 in the most significant bit (MSB) of source address (SA) filed in the media access control (MAC) header. For nodes on the same ring, note that routing information is unnecessary.

Broadcast packets on a token ring always have their routing information bit turned on (Figure 1), indicating to bridges between the source and destination nodes that the route is to be inserted into the packet. For non-broadcast packets, each source node (SN) determines whether routing information is necessary, and hence either puts a 1 into the MSB of the source address and appends the routing control field, or it doesn't. If the source routing bit is set to one, the routing information field (RC) is inserted between the source address (SA) field and the information field. With the source routing bit set to 0, the information field would immediately follow the source address (SA) field.

Each bridge puts its adjoining segment number into the next available SN field in the routing information field. Thus, a destination node could receive multiple packets from multiple bridges, and thus have several routes back to the source.


Note:
The term broadcast here refers to link-level broadcasts. This is not to be confused with AppleTalk broadcasts to the AppleTalk address $FF. These types of broadcasts are destined only for AppleTalk nodes on the link, not necessarily all nodes on the link.)


Figure 1. Routing Information and Routing Control Fields.

Figure 1. Routing Information and Routing Control Fields

Types of Broadcasts

At present, packets can be broadcast in one of three ways. The type of broadcast is defined by three bits in the routing control field of the routing information field (see Figure 1).

The types of broadcasts are as follows:

100

All-routes broadcast, non-broadcast return. Broadcast packets of this type will travel along any possible path to the destination; thus the number of packets received at the destination will equal the number of routes to the destination node. Packets coming back to the source will travel along the same route, in reverse order, as they did going to the destination.

110

Single-route broadcast, all-routes broadcast return. Broadcast packets of this type will travel along a single route, passing through designated bridges to the adjoining segment. Packets coming back to the source can possibly travel along multiple paths to reach the source; thus, the first packet received back at the source will indicate the best route between the destination and the source. A network administrator will set up the designated bridge as one that will forward this kind of broadcast. (Note that rev F of the TMS380 Adapter Chipset User's Guide Supplement, which describes these bits on page 7-4, incorrectly documents the bits, 111, to this type of broadcast.)

111

Single-route broadcast, non-broadcast return. Broadcast packets of this type will travel along a single route, passing through designated bridges to the adjoining segment. Packets coming back to the source will travel along the same route, in reverse order, as they did going to the destination. A network administrator will set up the designated bridge as one that will forward this kind of broadcast. (Note that rev F of the TMS380 Adapter Chipset User's Guide Supplement, which describes these bits on page 7-4, incorrectly documents the bits, 110, to this type of broadcast.)

For directed transmissions between several bridges, the broadcast bits are 000. This indicates that the route is already present in the segment numbers, and the packet travels in a directed manner to the destination.

Back to top

Source Routing on Apple's TokenTalk Card

Apple's TokenTalk Card is built upon the Macintosh Coprocessor Platform. Much of the TokenTalk software consists of dynamic A/ROSE tasks running on the card. Developers can use the services of TokenTalk Prep (documentation of which is available on the TokenTalk NB Programmer's Guide), and the actual source routing is done with a SNAPXmit. SNAPXmit does the exact same thing as LLCXmit, but it doesn't do source routing for you, nor do you have to specify a service access point (SAP).

Essentially, we have two types of packets to transmit: broadcast packets and individual directed packets.

For broadcast packets, which include functional address transmissions, group address transmissions, and all-stations broadcast transmissions, we add source routing information. For TokenTalk, the broadcast type is all-routes broadcast, non-broadcast return.

For individual directed packets, we have to determine if the destination is on our ring or not. If it is not then we must append the routing information to the packet. Where does the route come from? If we've been smart, we've been gathering routes from any broadcast packet we receive, and saving them away. We want to have a couple of tables on which to store the information: a table that maps destination nodes to ring numbers (segment numbers), and a table that maps ring numbers to routes. If we are asked to transmit an individual packet, we simply look up the destination ring number (compare it with our own ring number to determine whether routing information is necessary) and then look up the route for the ring we just looked up. Once we have a match, we just append the routing information and transmit the packet. Everything's hunky- dory.

"But," you ask, "what if I don't have the route?" That is, what if there's no ring number mapped to the destination address? You'll have to find the best route and then send it along. We do this by queuing the original request momentarily, packing up a Logical Link Control (LLC) test command packet, putting the desired destination address into the packet, and setting the broadcast type to "single-route broadcast, all-routes broadcast return." This means we'll get back (potentially, if there's more than one route) many responses with routes in them. Hopefully the first such packet we receive will indicate the best route because it took the shortest amount of time to reach us.

Now, you're probably asking yourself: "What did you mean when you said, `If we've been smart, we've been gathering routes from any broadcast packet we receive'?" Even better, every TokenTalk packet broadcast at the link layer will have this source routing information in it. Therefore, every TokenTalk packet will contain the route back to the source and we can "glean" this information and store it in our tables. This is where the direction bit comes in handy. If the direction bit is 1, then the furthest segment is the last segment number in the routing information field, that is, the rightmost. Conversely, if the direction bit is 0, then the furthest segment is the first segment number in the routing information field, that is, the leftmost. This furthest segment indicates the ring number the source is actually on, and we can add this source ring number to our table. We can also add (or update) our ring number to route table.

"What if the entries in this table just sit around--potentially after a node is no longer reachable?" That's a good question. Again, we'll use a common practice for such tables: each entry in our table should have some "age" associated with it, and when the "age" gets too old, we delete the entry from our table. The worst thing that can happen from such a deletion is we'll have to go through the route discovery process again.

Back to top

Conclusion

Source routing is necessary for any token ring link to function. Thus, hopefully, you have a clear recipe here for implementing that functionality in your code.

Back to top

References

TokenTalk NB Programmer's Guide, Chapter 2, "Source Routing Support", APDA, M0827LL/A

IBM Token-Ring Network Architecture Reference, Chapter 3, "MAC Frame Format", IBM Corporation, SC30-3374--01

TMS380 Adapter Chipset User's Guide, Texas Instruments, SPWU001D

TMS380 Adapter Chipset User's Guide Supplement, Chapter 7, Texas Instruments, SPWU003

J. Scott Haugdahl: Inside the Token-Ring, Chapter 3, "Standards and Protocols", Architecture Technology Corporation, 1986

Back to top

Downloadables

Acrobat gif

Acrobat version of this Note (120K)

Download


Back to top


Did this document help you?
Yes: Tell us what works for you.
It’s good, but: Report typos, inaccuracies, and so forth.
It wasn’t helpful: Tell us what would have helped.