Since it is possible to have multiple modules, running on multiple computers, the system is both scalable and redundant. When the load increases the system administrator can start new instances of any module, thereby removing any bottlenecks detected.
In a running Wayfinder Server system each type of module has one of the running modules as leader and the others are availables. The leader is the only one that listens on the leader multicast address that the frontends initially talks to. The leader gets information from all the availables about their load and loaded resources, which maps it has, and can direct frontends to a suitable available.
Voting is the way for a multiple running processes, of a specific type of module, to come together and select one of the running processes as a leader.
This section covers the voting mechanism used to make sure that there is exactly one leader among the modules of a certain type.
Voting starts if one (or more) of the following statements are true.
HeartBeatPacketin a certain amount of time. This usually means that there is no leader on the same net.
HeartBeatPacketfrom another leader and both leaders know about more than one availables.
HeartBeatPacketfrom another %leader% and both leaders know about zero availables.
No voting will occur if a leader with more than one available receives a
HeartBeatPacket from a leader with zero availables. The leader with zero availables will turn into an available when it gets the other module’s
When voting is initated the module initiating the voting will become available and send
VotePacket packets to the other modules using the multicast addresses for leaders and availables. The modules receiving the packets will turn into availables and compare the
*VotePacket to its own data, see Comparing VotePackets below. If it finds itself better than the module sending the first VotePacket it replies with its own
VotePacket or else it ignores the packet. No replies should be received by the best module, since the other modules shouldn’t reply to better packets. The voting is finished when the best module doesn’t receive any packets after resending its
VotePacket a few times. This module will then become a leader.
VotePacket packets are compared by
rank is a value given to the module by the operator. Better rank always wins. If the ranks are the same the IPs will be compared and if they are the same too, the ports will be compared. This way two modules will always have a different
This is a brief description of the load sharing mechanism in the modules. There can be many modules of a specific type running at the same time. This means that a
RequestPacket can be handled by any one of several modules. To share the work load in an efficient manner, the
RequestPacket is first delivered to a leader module. The leader module then decides which of the other available modules that should do the job. It is also possible for the leader to process the
RequestPacket by itself. The
RequestPacket is first sent via multicast to one IP address that only the leader listens to. If the leader decides that the packet should be sent to one of the available modules, it sends the packet to the IP address of that module. Note that packets for the leader are sent via multicast, but the only module listening to this is the leader, so it works fine. In order for the modules to be able to have a leader, and for the leader to be able to decide who should take care of an incoming
RequestPacket, the modules also have a few administrative routines. At regular intervals, the leader multicasts heartbeat packets to the available modules. When an available module receives a heartbeat packet, it immediately multicasts a statistics packet to the leader, who then uses these statistics to decide which modules are available to handle an incoming
RequestPacket. If the leader module dies, the available modules will detect this, because there will be no heartbeat reaching them for a while. When an available module detects there is no leader module, it starts sending packets saying it wants to be the new leader. The modules now decide by vote who should be the new leader module. The one that become the leader starts sending heartbeats (to the leader-multicast address), and listens to the multicast address for an incoming
In addition to the load balancing inside the cluster (between the Modules that carry out the actual tasks) IP load balancing between the interfaces in done by the operating system (Linux Virtual Server). This ensures that requests from the clients are distributed between the Interfaces and that a malfunctioning Interface is disconnected (even if this is very unlikely). There is no dedicated computer for the IP load balancing but rather some of the machines in the clusters handle this.
Suppose the user sends a request for a route from A to B. The server then creates one Request to handle it. A search module (SM) takes the name of a place (mainly street name, company name or point of interest) and returns its ID number. A route module (RM) takes the IDs of two places and returns a route between them. The Request can therefore have its question answered by first sending two
RequestPacket packets to SMs (there can be more than one SM, so this operation can be performed almost in parallel). Suppose A has ID 17 and B has ID 43. When both IDs have been received by the Request, it asks the RM for a route from 17 to 43. When the Request receives this route, it has all the information it needs. The answer is sent to the user, and the necessary debiting information is send to the module responsible for logging this information and the Request is destroyed. A slightly different situation occurs when the user wants a map of a certain area. Let us assume that the user requests a map over an area enclosed by the rectangle with corners in (x1; y1) and (x2; y2). As before, when the server receives a user request, a Request is created. The Request sends a
RequestPacket with the coordinates to a map module (MM). There is a lot of information in an entire map, so to send many datagrams to the Request, would be inefficient. Instead, the MM returns a port number and its IP address. The server then starts a TCP/IP connection with the MM, and glues it to the TCP/IP connection already established between the server and the user. That way, the MM can send all the map data directly to the user, which is a lot more efficient. When all data has been sent, the TCP/IP line is disconnected, and the Request is deleted.
A collection of applications that acts like a server from the perspective of clients of the Wayfinder Server. Main task is to parse and translate the incoming request, ask the modules for the answer, format the reply and send that back to the caller.
The frontends are named servers in the source tree and are also called interfaces since they connect the clients to the server.
Interface to clients with a proprietary protocol that uses little memory, cpu power, and bandwidth.
Handles all different kind of requests in XML-format. It is possible to access most of the MC2 functionality via the generic XML API.
Processes incoming traffic information and sends it to InfoModule for storage.
This class of applications perform the actual calculations and look-ups for each request. Acts like a server from the frontends perspective. The backends are called modules internally in MC2.
Sends information to external servers. This information can be location updates to another system.
See External connections, PosPush, section in Server functions.
Handles the sending of e-mails and MMS messages.
This module performs searches in remote databases, e.g. white page databases located at the information provider. Designed to make it easy to add new protocols, currently supports XML based and a few proprietary formats.
See Server functions External Search.
Draws map images (PNG, GIF, WBMP).
GfxFeatureMap is a map over an area with a number of
GfxFeature maps are created in the MapModule and used by the GfxModule and TileModule to make maps. A
GfxFeature represents a thing on a map such as street, builtup area, ferry, island etc. A
GfxFeature has a number of
GfxPolygons describing the extent of the
GfxRoadFeatureRepresents a part of a route.
GfxSymbolFeatureRepresents a generic symbol to show on map. May be user defined image and name.
GfxTrafficInfoFeatureRepresents traffic information (such as an accident, road work etc.).
Collects and stores information about dynamic changes in traffic and distributes it to the users who need it.
Stores and handles the map. This includes sending it to the servers and other modules that needs it.
Performs the route calculations.
See The routing algoritm for details on how routing is made.
Sends and receives SMS messages via an SMSC or other SMS service.
Searches for locations expressed as strings, for example street names, company names and business categories.
See section Search.
Creates the proprietary vector map format that is used to stream maps to the clients.
The Tile maps starts their creation in
GfxTileFeatureMapProcessor in the MapModule as a
GfxFeatureMap that is sent, by a frontend, to TileModule and converted to a Tile map.
Manages all the (end) users of the system, including their billing and user profiles.
This is all logical and geographical data that we have, describing the world. Examples of information are streets, logical connections between streets, built-up areas, Subject to change without notice municipals, point-of-interests and lakes. The maps are stored in a proprietary format to maximize the performance.
A generic relational database is used to store information about the users of the system, including the user profile, transactions and active subscriptions.
The servers communicate with the Modules using packets. The packets consist of binary data that can be sent between computers and programs and consist of binary data that can be read and written using the class
Packet and its subclasses which will be described in this section.
The data that is to be sent between the different parts of the MC2-server is usually not in the form of a byte array, which it must be when sending it using network protocols.
Packet contains helper functions for reading and writing data to a byte array that is independent of the byte ordering of the sender and recipient computers.
Packet uses the bigendian byte ordering which is the same as network order. Network byte ordering was chosen because most operating systems have (optimized) functions (
htonl, etc.) to convert from the native byte order to network order since these functions are needed when using TCP/IP. The values stored in the packets are aligned to the same offset as the size of the value, i.e. 16-bit values are stored on even addresses and 32-bit values are stored on addresses that are evenly dividable by 4.
Packet class has the following data members:
bufferByte array containing the actual data.
bufSizeThe number of allocated bytes in the buffer.
lengthThe number of bytes actually used in the buffer. The buffer of the
Packetalways starts with a header containing information about who sent the packet, type of packet etc. It is documented in
Objects of the class
Packet are only used when sending and receiving data from the network. When information is written to or read from a
Packet a subclass with more suitable functions is used. When a
Packet is read from the network it is cast to the right kind of packet by looking at the type field in the packet header. For this reason, subclasses to
Packet cannot contain any data members of their own. Most of the packets in the MC2 system should inherit from one of
ReplyPacket. These contain extra header information for packets sent from servers to modules and packets returned from modules to servers respectively.