Routing the FLYWAY Beamcars

Advice is what we ask for when we already know the answer but wish that we didn't.

We have written about the theory of routing, as it applies to the FLYWAY® system on the page titled "Optimization of travel routes". As you have noted (if you have read that webpage), we presented a simplified, 2-dimensional routing table, that only used the travel time as basis for routing decisions. in reality, other factors than travel time have to be considered as well, such as those mentioned in Chapter 5 on that page.		List of contents: Adapting OSPF for FLYWAY Route Selection Criterias How to implement path and routing tables

FLYWAY uses the OSPF-protocol to gain access to 7 useful selection criteria for its own, specific use. OSPF is short for "Open Shortest Path First" and is ordinarily used by servers on the Internet. It should be emphasized here, to avoid confusion with the reader, that FLYWAY will use the OSPF-protocol such as it is formed, but for its own, specific purposes. These purposes are determined solely by how the sending and receiving applications choose to act upon the information which is sent by using this protocol. Thus, notwithstanding that the intended purpose of OSPF is to regulate data traffic, FLYWAY will use this same information to regulate beamcar traffic. So, how is FLYWAY going to implement its version of OSPF?

OSPF-packets are exchanged between routers. The logical choice for computers that will fill this role would be the node computers in the beam network. The node computers are the first to find out about changes in the network and the general traffic situation. OSPF requires a hiearchical router structure in order to function. This is because some degree om supervision is required over how update messages and other communication is exchanged between the routers. One router will thus be "master", another router will be "backup" in case the master should fail, and the rest of the routers should be logically arranged so that they correspond to the topological positions of the node computers where these routers reside. In order to avoid being confused; regard the router as an application program running on each node computer. OSPF uses the Link State Protocol, and normally creates databases in every router, containing the states of the links in their neighborhood, or, depending on configuration; the whole network. In the case of FLYWAY, the routers will instead construct path tables and routing tables for the physical beam network.

These routing tables are duplicated in the beamcars. To reduce dependence on good communication and increase operative resilience, the FLYWAY beamcars will control themselves, rather than being remote-controlled by the nodes. Depending on network size, the individual beamcar will have the whole network in its table, or only the local part. Whenever an approaching beamcar announces itself to an upcoming node, it will also announce the time of its latest routing table update. The node will check this update time against its log of updates and, if required, send all the updates that has been made after that time, back to the beamcar in connection with its acknowledgement message. The beamcar will include these updates in its routing table. Thus, the parts of OSPF that FLYWAY uses are: the datapackets, the timers, the router configurations and its calculating algorithms. But not its routing table structure and final application. FLYWAY will complement the Type of Service codes with additional codes for its own use. See table 2:3 further down.

FLYWAY uses the OSPF-protocol in its communications to give priority to some routes (and some vehicles) when deciding upon routing directions. These evaluations would be added to the nodes' routing tables, both manually and dynamically, as the occassions arise. Figure 2:1 illustrates different communications protocols that could be used to provide both static and dynamic routing information. Those interested in this can read more under the heading "For the Curious", below. In the case of dynamic updates, the altered evaluations would reflect changes in the network, and hese would be propagated from one node to the next by way of LSA-packets (LSA = Link State Advertisement, the data packet types used by OSPF). Let's see examples of how they could be used.

Figure 2:1

Chapter 16 of RFC 1583 explains how the routing table on an OSPF router is constructed and maintained. There are 7 parameters that could be derived from the OSPF procedure that we are interested in: Capacity of a Link Delay factor of a Link Throughput factor of a Link Number of packets waiting for transmission on a Link Load balancing between Links Security requirements of a Link Number of hops. OSPF uses the destination address and Type of Service (TOS) information in an IP datagram header to determine the route for the package. The method used to find the optimum route is called cost metrics. Understanding Cost Metrics Using the example in figure 2:2 (which is essentially the same as the figure 2 example in RFC 1583) and taking router 6 as our departing point, OSPF sets up the destination tree shown in figure 2:3 below. Edges that are not marked with a cost have a cost of zero (these are network-to-router links). Routes to networks N12 - N15 are external information. Figure 2:3 From this tree we can derive table 2:1 (or vice versa), showing the portion of Router RT6's routing table that lists local destinations. You will note, when comparing with figure 2:2, that: Only the costs when moving from RT6 are included Not all possible routes are included in the tree, only the cheapest one to each destination. The numbers in the "distance" column are (of course) arrived at by straight adding of the partial costs. Thus, to the cost of getting to Network 1 (N1) by way of RT3 - N3 - RT1 - N1 is 6 + 1 + 1+ 3 = 11. Table 2:1 Destination Next Hop Distance N1 RT3 11 N2 RT3 10 N3 RT3 7 N4 RT3 8 Ib * 7 Ia RT10 12 N6 RT10 8 N7 RT10 12 N8 RT10 10 N9 RT10 11 N10 RT10 13 N11 RT10 14 H1 RT10 21 RT5 RT5 6 RT7 RT10 8 OSPF supports two types of external metrics. Type 1 external metrics are equivalent to the link state metric. Type 2 external metrics are greater than the cost of any path internal to the AS (AS = Autonomous System). Use of Type 2 external metrics assumes that routing between AS'es is the major cost of routing a packet, and eliminates the need for conversion of external costs to internal link state metrics. As an example of Type 1 external metric processing, suppose that the Routers RT7 and RT5 in figure 2:2 are advertising Type 1 external metrics. For each external route, the distance from Router RT6 is calculated as the sum of the external route's cost and the distance from Router RT6 to the advertising router. For every external destination, the router advertising the shortest route is discovered, and the next hop to the advertising router becomes the next hop to the destination. Both Router RT5 and RT7 are advertising an external route to destination Network N12. Router RT7 is preferred since it is advertising N12 at a distance of 10 (8+2) to Router RT6, which is better than Router RT5's 14 (6+8). The table below shows the entries that are added to the routing table when external routes are examined: Table 2:2 Destination Next Hop Distance N12 RT10 10 N13 RT5 14 N14 RT5 14 N15 RT10 17 Using OSPF to route FLYWAY Traffic All OSPF link state advertisements (with the exception of network links advertisements) specify metrics. In router links advertisements, the metrics indicate the costs of the described interfaces. In summary link and AS external link advertisements, the metric indicates the cost of the described path. In all of these advertisements, a separate metric can be specified for each IP TOS. The encoding of TOS in OSPF link state advertisements is specified in table 2:3below. This table relates the OSPF encoding to the IP packet header's TOS field (defined in RFC 1349). The OSPF encoding is here expressed as a decimal integer, and the IP packet header's TOS field is expressed in the binary TOS values used in RFC 1349. Table 2:3 TOS values Binary Standard meaning Proposal for FLYWAY 0 0000 normal service normal service 2 0001 minimize monetary cost minimize monetary cost 4 0010 maximize reliability maximize reliability 6 0011 - capacity 8 0100 maximize throughput maximize throughput 10 0101 - delay 12 0110 - cars waiting 14 0111 - load balancing 16 1000 minimize delay minimize delay 18 1001 - security 20 1010 - - 22 1011 - - 24 1100 - - 26 1101 - - 28 1110 - - 30 1111 - -

For the Curious: the OSPF Protocol (Unfortunately, we cannot provide a basic course in TCP/IP networking. You will have to be quite familiar with networking and with TCP/IP in order to understand this text.) As can be seen in figure 2:1 above, the routing table can be kept updated from different sources, using different communication protocols, and depending on whether the update information is static or dynamic. The static information would in most cases be added by way of human intervention, as the beam network is altered and expanded. But it is the task of the sources of dynamic information to keep a complex data network functioning satisfactorily. One of the protocols suited to provide dynamic information from different sources is OSPF. The OSPF-protocol was developed by the Internet Engineering Task Force, with the aim of enabling servers to route messages the "best" way through the Internet. The term "shortest path" is actually an inaccurate description of how this protocol works. It´s rarely the "shortest path" which is the "best" path for routing a message. Other factors are more important. A better term would be "optimum path". A quite exhaustive explanation of the OSPF protocol can be found in RFC 1583. Figure 2 from RFC 1583 is reproduced here, for your convenience (figure 2.2 below). It shows an example of how various TCP/IP-based networks (Indicated by Nxx) are tied together by OSPF-routers. H1 indicates a host, which has a SLIP connection to router RT12. Router RT12 is therefore advertising a host route. Lines between routers indicate physical point-to-point networks. The only point-to-point network that has been assigned interface addresses is the one joining routers RT6 and RT10. Routers RT5 and RT7 have EGP connections to other Autonomous Systems. A set of EGP-learned routes have been included for both of these routers. Refer to RFC 1583. for further details. Figure 2:2 The numbers at the entrance to every link indicates the "cost" of using that link, in that direction. Thus, the cost of going from RT3 to RT6 is 8, but the cost of going in the opposite direction (from RT6 to RT3 is only 6. OSPF uses the destination address and Type of Service (TOS) information in an IP datagram header to determine the route for the package. From a routing table, kept updated in every router, which contains the topology of the network, an OSPF router determines the "best" path by using cost metrics, which factor in relevant criteria for what constitutes the optimum path. OSPF allows for the division of a large autonomous network into smaller areas, each with its own gateway and routing algorithms. Movement of messages between these areas take place over the backbone, which is usually a conduit that can handle huge amounts of data. OSPF itself (as a communications protocol) functions by sending 4 general types of messages: Every router sends a HELLO message at certain intervals as a broadcast to announce its presence. Should these messages cease for a long enough period, that router would be declared as "dead" by the other routers, until such time as it starts transmitting again. When changes occur in a router table, that router will send an update message as a broadcast to the other routers, so that they are kept aware of the situation in the network from time to time, and can route messages accordingly. When a router finds its topological table to be corrupted (such as entries missing or out of date) it will send a Link State Request Packet to its nearest neighbors. The answer would be an update message. At regular intervals, every router will send a a Link State Update Packet to its nearest neighbors. This packet contains fields for each router link and the type of service provided in each link. The update packets are called advertisements and are of 4 types: A Router Links advertisement provides information on a local router´s connections in an area. This is a broadcast message, i.e. without a specific addressee. A Network Links advertisement provides a list of routers that are connected to a network. This is also a broadcast message. A Summary Links advertisement contains information about routes outside the area. It is sent by border routers to their entire area. An Autonomous System Extended Links advertisement contains information on routes in external autonomous systems. It is used by boundary routers but covers the entire system. All routers run the exact same algorithm, in parallel. From the topological database, each router constructs a tree of shortest paths with itself as root. This shortest-path tree gives the route to each destination in the Autonomous System. Externally derived routing information appears on the tree as leaves. OSPF calculates separate routes for each Type of Service (TOS). When several equal-cost routes to a destination exist, traffic is distributed equally among them. The "cost" of a route is described by a single dimensionless metric. OSPF allows sets of networks to be grouped together. Such a grouping is called an "area". The topology of an area is hidden from the rest of the Autonomous System. This information hiding enables a significant reduction in routing traffic, since all nodes don´t need to know all details of other areas. Also, routing within the area is determined only by the area's own topology, lending the area protection from bad routing data. An area is a generalization of an IP subnetted network. OSPF enables the flexible configuration of IP subnets. Each route distributed by OSPF has a destination and mask. Two different subnets of the same IP network number may have different sizes (i.e., different masks). This is commonly referred to as variable length subnetting. A packet is routed to the "best" (i.e., longest or most specific) match. Those host routes whose masks are "all ones" are considered to be subnets (0xFFFFFFFF). TOS-based routing OSPF can calculate a separate set of routes for each IP Type of Service (TOS). This means that, for any destination, there can potentially be multiple routing table entries, one for each IP TOS. The IP TOS values are represented in OSPF exactly as they appear in the IP packet header. In order to differentiate routes based on TOS, separate interface costs can be configured for each TOS. For example, there could be multiple costs (one for each TOS) listed for each interface. A cost for TOS 0 ( = "normal" service; see table 2:3 to the left) must always be specified. When interface costs vary, based on TOS, a separate shortest path tree is calculated for each TOS. In addition, external costs can vary based on TOS. For example, in figure 2:2, router RT7 could advertise a separate type 1 external metric for each TOS. Then, when calculating the TOS X distance to Network N15 ("X" refers to the TOS value in the first column of table 2:3), the cost of the shortest TOS X path to RT7 would be added to the TOS X cost advertised by RT7 for Network N15. All OSPF implementations must be capable of calculating routes based on TOS. However, OSPF routers can be configured to route all packets on the TOS 0 path, eliminating the need to calculate non-zero TOS paths. This can be used to conserve routing table space and processing resources in the router. These "TOS-0-only" routers can be mixed with routers that do route based on TOS. TOS-0-only routers will be avoided as much as possible when forwarding traffic requesting a non-zero TOS.

How are the Type of Service values implemented? Well, for every path in the beam network (i.e. from one adjoining node to another) the path table would contain an alternative calculated cost for each TOS value that is set. If Nodes 4 and 5 in figure 2:4 have TOS 0 (mandatory), 2, 6 and 8 set, 4 cost-alternatives would thus be created between them. Other parameters would then determine which one of these alternatives should apply in each situation. Figure 2:4 The proposed additions for FLYWAY use in the rightmost column of table 2:3 would have the following practical uses: Capacity of a Link: Could be used to limit the size or weight of vehicles using this route. This would mean that some routes are simply off-limits for certain beamcars, maybe at certain times or under certain conditions. TOS 6 on beam network paths that are thus limited would require that the beamcar knows that certain TOS 6 -alternatives are no available.

Delay factor of a Link: Could be used to tell other nodes the highest speed permitted on this route, or, rather, give the time that it would take to travel along this route. TOS 10 would be used. Throughput factor of a Link: Could be used to estimate the number of vehicles per time unit that a certain path can handle at the present (thus, a figure that could vary over time). The reason being, of course, that the route has to receive traffic from feeder beams. TOS 8 applies. Number of packets waiting for transmission on a Link: Could be used to tell other nodes that a node is overloaded and cars are queueing. The cost of using this path should be somewhat proportional to the queue situation. Some complex calculations would be involved. TOS 12 applies. Load balancing: This is the normal state; all cost factors on parallel routes being equal, OSPF-routers see to it that the traffic is evenly distributed among these inks. This normally corresponds to TOS 0. There might conceivably be reasons to distribute traffic un-evenly; if, for instance, one route passes by a hospital or similar place, where one would want to keep the traffic at a minimum, so long as there are other comparable routes available.hospital, it might be motivated to redirect such traffic over other routes. TOS 14 has been reserved for this purpose.

Security requirements of a Link: Could be used to indicate that certain routes are restricted to certain cars or type of cars. Maybe the routes are privately owned? Or tourists might not be allowed into military restricted areas. TOS 18 would be used. Number of hops: Is meant to ensure that data packets pass by as few routers as possible, thus reducing the total workload of the routers. Could be used to make some beamtraffic routes less attractive than other alternatives. In addition to this, beamcars would have to be dynamically classified in such a manner that the nodes would take this into account and weigh it together with the information obtained through the parameters listed above. Thus, a beamcar doing ambulance service would be given highest priority during emergency transport, while, on the other end of the scale, empty cars returning to depots or going in for maintenance would be given lowest priority.