Routing

Routing bezeichnet in der Telekommunikation das Festlegen von Wegen für Nachrichtenströme bei der Nachrichtenübermittlung über vermaschte Nachrichtennetze bzw. Rechnernetze. Die Routing-Protokolle sorgen für den Austausch von Routing-Informationen zwischen den Netzen und erlauben es den Routern, ihre Routing-Tabellen dynamisch aufzubauen.

Auch Battleship erlaubt es Ihnen ein eigenes Routing zu implementieren, beispielsweise unter Nutzung der bereits erwähnten verteilten Hashtabelle. In unserer Netzwerkbibliothek wird als Einstieg eine sehr einfache Routerklasse mit dem Namen SimpleRouter definiert.

public class SimpleRouter implements RouterInterface
{
    /**
     * The constructor.
     *
     * @param peer
     */
    public SimpleRouter(Node peer)
    {
        peer_ = peer;
    }
 
    /**
     * Returns the peer info object of a given peer id.
     * 
     * @param peerid    a peer id
     * @return  returns a PeerInfo object or null if unknown
     */
    @Override
    public PeerInfo route(String peerid) 
    {
        if( peer_.getPeerKeys().contains( peerid ) ) {
            return peer_.getPeer( peerid );
        } else {
            return null;
        }
    }
 
    /** The peer node */
    private Node peer_;
}

Der SimpleRouter leitet Anfragen direkt an den aus der Hashtabelle ermittelten Peer weiter. Hierzu werden keine nennenswerten intelligenten Algorithmen verwendet. Das System kann allerdings zu einem beliebigen Zeitpunkt in der Zukunft um eine neue Routerklasse ergänzt werden.

/**
 * This method attempts to route and send a message to the specified peer,
 * optionally waiting and returning any replies. It uses the Node's routing function
 * to decide the next immediate peer to actually send the message to, based on
 * the peer identifier of the final destination. If no router function (object)
 * has been registered, it will not work.
 *
 * @param pid   the destination peer identifier
 * @param msg   the message
 * @param waitReply whether to wait for reply(ies)
 * @return list of replies (may be empty if error occurred)
 */
public List<Message> sendToPeer(String pid, Message msg, boolean waitReply)
{
    PeerInfo peerInfo = null;
 
    if( getRouter() != null ) {
        peerInfo = getRouter().route( pid );
    } else {
        logger_.severe( String.format( "Unable to route %s to %s", msg.getType(), pid ) );
        return new ArrayList<Message>();
    }
 
    return connectAndSend( peerInfo, msg, waitReply );
}

Man unterscheidet zwischen vier wesentlichen Routingschemen.

• Unicast liefert eine Nachricht an einen spezifizierten Knoten;
• Broadcast liefert eine Nachricht an alle Knoten im Netzwerk;
• Multicast liefert eine Nachricht an eine bestimmte Gruppe von Knoten im Netzwerk, die an dieser Nachricht interessiert sind;
• Anycast liefert eine Nachricht an jeden Knoten innerhalb einer Gruppe von Knoten, typischerweise den an der Quelle nächstgelegenen.

Kleine Netzwerke verwenden oft manuell konfigurierte Routingtabellen (Static Routing), während größere Netzwerke komplexe Topologien abbilden und sich schnell wandeln, was eine manuelle Anpassung der Routingtabellen erschwert. Battleship verwendet mit dem aktuellen SimpleRouter Unicast um Nachrichten an Knoten im Netzwerk auszuliefern.

Bei allen Verbindungen handelt es sich um bidirektionale, byte-orientierte, zuverlässige Datenströme zwischen zwei Endpunkten. Die Netzwerkbibliothek basiert vollständig auf dem Transmission Control Protocol (TCP) und verzichtet auf das UDP. In TCP sind Multicast und Broadcast auf Internet-Protokoll-Ebene nicht möglich, da es es sich bei TCP stets um eine verbindungsorientierte Punkt-zu-Punkt-Verbindung (Unicast) handelt. Im Anwendungsprotokoll lassen sich allerdings Mechanismen implementieren, die eine effizientere Ausnutzung der individuellen Bandbreite gestatten. Das übergeordnete Protokoll definiert Routingschemen, z.B. baumbasierte Multicast-Algorithmen, die Nachrichten gezielt an Gruppen ausliefern und diese effizient über das P2P-Netz routen. Schlußendlich ist es auch möglich die Bibliothek zu erweitern, so dass UDP-Pakete gesendet und empfangen werden können.

Es ist nur UDP-Sockets gestattet Broadcast und Multicast zu nutzen. Da die herkömmlichen, im Internet eingesetzten Router in aller Regel nicht Broadcast- und Multicast-fähig sind, bleiben Multicast-fähige Teilnetze im Internet isoliert und bilden so genannte Multicasting-Inseln. Diese Inseln können mittels Tunneling, also durch Kapseln eines Multicast-Pakets in ein Unicast-Paket, überbrückt werden und bilden so ein weltumspannendes Multicast-Netz, den MBONE.

Bootstrapping

In einer P2P-Anwendung muss ein neuer Peer zunächst die Adresse von einem zweiten Peer kennen, der bereits mit dem Netzwerk verbunden ist. Ein Netzwerk ist vergleichbar mit einem Spinnennetz. Viele Peers bilden ein gemeinsames Netzwerk. Netze können auch fragmentieren, so dass sich Subnetze bilden. Dies kann gewollt oder nicht gewollt sein.

Bevor ein Peer online gehen kann und zu einem Bestandteil eines bestehenden Netzwerks wird, muss das sogenannte „Bootstrapping“ erfolgen. Unter „Bootstrapping“ versteht man den Vorgang, den ein Knoten durchläuft, wenn er sich in ein bestehendes Netzwerk einklinkt. Es bezeichnet in der Informatik einen Prozess, der aus einem einfachen System ein komplizierteres System aktiviert. Für diesen Prozess wird eine Startadresse benötigt, ähnlich wie Sie bei einer Telefonkonferenz die Telefonnummer von mindestens einem weiteren Teilnehmer kennen müssen.

Bekannte P2P-Anwendungen, wie eMule, nutzen spezielle Techniken, wie Kademlia. Dabei handelt es sich um eine besondere Technik für Peer-to-Peer-Netze, welche eine verteilte Hashtabelle implementiert. Kademlia legt Art und Aufbau des Netzes fest. Auch in Kademlia muss ein Knoten, der dem Netz beitreten möchte, zuerst den mit „Bootstrapping“ benannten Prozess durchlaufen: In dieser Phase erhält der Algorithmus von einem Server oder Benutzer im Netzwerk die IP-Adresse einiger Knoten, die bereits im Kademlia-Netz bekannt sind. Von diesen ersten Knoten erhält er nun auch die IP-Adressen weiterer Knoten, so dass keine Abhängigkeit mehr von einzelnen Knoten besteht.

Viele Anwendungen, wie auch ICQ, nutzen zentrale Server mit einer statischen IP-Adresse, um das Problem zu umgehen. Der Benutzer muss sich nicht weiter darum kümmern und betätigt lediglich einen Connect-Button. Alle Netzwerkteilnehmer registrieren sich bei diesem zentralen Server, so dass Adressen problemlos ausgetauscht werden können.

Die Klasse BattleshipNode stellt eine spezielle Methode für die Konstruktion eine Netzwerks beim „Bootstrapping“ zur Verfügung. Diese Methode baut in einem rekursiven Aufruf das vollständige Netzwerk für den Peer auf, sobald einer erste Verbindung mit einem Netzwerkteilnehmer etabliert wurde.

/**
 * Builds the p2p network for this node bootstrapping the new peer,
 * recursively.
 * 
 * @param host  the host
 * @param port  the port number
 * @param hops  number of hops
 * @return  returns false if peer couldn't be added
 */
public boolean buildNetwork(String host, int port, int hops)
{
    logger_.fine( "Building network." );
 
    if( maxPeersReached() || hops <= 0 )
        return false;
 
    PeerInfo peerInfo = new PeerInfo( host, port );
 
    // Send a PEERINFO message to get detailled peer infos, wait for reply
    Message msg = new PeerMessage( MessageType.PEERINFO.toString(), getMyInfo().getId(), "" );
    List<Message> resplist = connectAndSend( peerInfo, msg, true );
 
    // No reply, return
    if( resplist == null || resplist.size() == 0 )
        return false;
 
    // We have the peer info data, proceed...
    List<String> infos = resplist.get( 0 ).getStringTokens();
 
    // Abort recursive search, when the pid is already known
    if( infos.size() != 6  || getPeerKeys().contains( infos.get( 0 ) ) )
        return false;
 
    logger_.fine( "Contacted " + infos.get( 0 ) );
 
    // Now parse received infos into our existing PeerInfo object
    peerInfo.setId( infos.get( 0 ) );
    // infos.get( 1 ), infos.get( 2 ) ... already stored
    peerInfo.setName( infos.get( 3 ) );
    peerInfo.setGender( infos.get( 4 ) );
    peerInfo.setBirthday( infos.get( 5 ) );
 
    // We try to join to the peer, too.
    msg = new PeerMessage( MessageType.JOIN.toString(), getMyInfo().getId(),
        new String[] { getMyInfo().getHost(),
                       Integer.toString( getMyInfo().getPort() ),
                       getMyInfo().getName(),
                       getMyInfo().getGender(),
                       getMyInfo().getBirthday() } );
 
    // Connect and send stuff
    String resp = connectAndSend( peerInfo, msg, true ).get( 0 ).getType();
 
    // If no answer, joining not possible
    if( !resp.equals( MessageType.REPLY.toString() ) )
        return false;        
 
    addPeer( peerInfo );    // Add the peer to our list
 
    // Check the web knowlegde of the remote peer, ask for his list
    resplist = connectAndSend( peerInfo, new PeerMessage( MessageType.LISTPEERS.toString(), getMyInfo().getId(), "" ), true );
 
    // Do a recursive depth call, first search to add more peers
    if( resplist.size() > 1 ) {
        resplist.remove( 0 );   // Number of peers, remove this
        for( Message pm : resplist ) {
            try {
                List<String> data = pm.getStringTokens();
                String nextpid = data.get( 1 ); // 0 is the senders id
                String nexthost = data.get( 2 );
                int nextport = Integer.parseInt( data.get( 3 ) );
                if( !nextpid.equals( getMyInfo().getId() ) ) {  // Not our pid
                    buildNetwork( nexthost, nextport, hops - 1 );
                }
            } catch( NumberFormatException e ) {
                logger_.info( "Can't parse port number! " + e.getMessage() );
            }
        }
    }
 
    return true;
}

Mithilfe der ersten Adresse wird der entsprechende Peer kontaktiert. Das System stellt diverse Handler und Nachrichtentypen, wie z.B. »JOIN« bereit, um den Austausch von Kontaktdaten zu erleichtern. Sobald ein Knoten mit einem anderen Knoten Kontakt aufgenommen hat, tauschen beide Knoten Informationen untereinander aus. So werden Kontaktadressen zu weiteren Knoten übermittelt. In einem rekursiven Aufruf werden diese neuen Adressen anschließend kontaktiert. So kann überprüft werden ob die Adressangaben korrekt sind. Darüberhinaus können spezifische Informationen von den Peers abgefragt werden.

Die Methode buildNetwork arbeitet sehr effektiv und konstruiert das vollständige Netzwerk. In der Regel wird diese Methode nur zu Beginn, beim „Bootstrapping“ aufgerufen.

Mit der Klasse BattleshipNode schließt sich der Kreis der Netzwerkprogrammierung in diesem Tutorial. Im Anhang finden Sie weitere Quelldateien, die zu dieser P2P-Bibliothek gehören, hier aber nicht angesprochen wurden. Sie können die entworfene Bibliothek problemlos in ihren eigenen Anwendungen weiterverwenden und neue Handler und Nachrichtentypen für ihr eigenes Anwendungsprotokoll definieren. So lassen sich auch Dateien übertragen oder Topologieinformationen austauschen. Den Möglichkeiten sind kaum Grenzen gesetzt. Wir beenden das umfangreiche Kapitel mit einem Diagramm, welches den prinzipiellen Aufbau und die Funktionsweise der Bibliothek demonstriert.

Abbildung 2: Interaktion zwischen zwei Peers

Das Model vervollständigen

Nachdem mit der Netzwerkkomponente ein wichtiger Bestandteil der Geschäftslogik implementiert wurde, ist es an der Zeit das Model zu vervollständigen. Das Model stellt eine Methode zur Generierung der Identifikationsnummer bereit. Diese Nummer wird an Spieler vergeben, die anschließend in der Lage sind ihre eigenen Daten im Model mithilfe dieser individuellen ID abzufragen.

/**
 * This is a utility function of the model. It generates an unique id
 * for all players. The id's are of the following format:
 * 
 * <code>object_classname:randombytes</code>
 *
 * @param object    the class object
 * @return          the unique id
 */
@Override
public String generateUniqueId(Object object)
{
    // Lets first generate a random string
    Random random = new Random();
    StringBuilder sb = new StringBuilder();
    String str = new String("QAa0bcLdUK2eHfJgTP8XhiFj61DOklNm9nBoI5pGqYVrs3CtSuMZvwWx4yE7zR");
    for( int pos = 0, i = 0; i < 100; i++ ) {
        pos = random.nextInt( str.length() );
        sb.append( str.charAt( pos ) );
    }
 
    String seed = new Date().getTime() + sb.toString();
 
    StringBuilder hexString = new StringBuilder();
    int numberToGenerate = 64;  // Total random bytes to generate
 
    try {
        // Generate pseudo-numbers using SHA1PRNG algorithm
        SecureRandom rng = SecureRandom.getInstance( "SHA1PRNG" );
        rng.setSeed( seed.getBytes() );
 
        byte randNumbers[] = new byte[numberToGenerate];
 
        rng.nextBytes( randNumbers );
 
        // Convert to hex
        for( int i = 0; i < randNumbers.length; i++ ) {
            String hex = Integer.toHexString( 0xFF & randNumbers[i] );
            if( hex.length() == 1 )
                hexString.append('0');
 
            hexString.append( hex );
        }
    } catch( NoSuchAlgorithmException e ) {
        e.printStackTrace();
    }
 
    // Concat class name with random bytes
    String id = object.getClass().getName() + ":" + hexString.toString();
 
    return id;
}

Die ID wird für jeden Spieler zu Beginn generiert. Im Model sind zahlreiche Methoden zur Datenabfrage definiert. Neben der Methode getString, die Zeichenketten in der aktuell eingestellten Sprache zurückliefert, kann der Spieler mit seiner ID auch sein eigenes Profil im Model abfragen, Schiffe auf seinem Spielfeld platzieren oder Felder markieren.

/**
 * Returns the name of this player.
 * 
 * @param id    the player id
 * @return  the players name
 */
@Override
public String getPlayerName(String id)
{
    // First check if the player is alive, has a profile
    if( playerExists( id ) == false ) {
        throw new IllegalArgumentException("Invalid player argument.");
    }
 
    return playerProfiles_.get( id ).getName();
}

Die Methode mark ist für die Markierung eines Feldes zuständig. Als ersten Parameter nimmt sie die ID des Spielers entgegen. Der zweite Parameter stellt einen Koordinatenpunkt auf dem Spielfeld dar. Das Model informiert über das Beobachter Entwurfsmuster alle beim Model registrierten Beobachter über Änderungen im Datenbestand.

/**
 * Marks a field.
 *
 * @param id        the player id
 * @param coord     the coords, which indicates where to mark
 * @return          true, if successful, false if not
 * @throws          eu.codeplanet.battleship.core.FieldOperationException
 */
@Override
public synchronized boolean mark(String id, Coordinate coord)
        throws FieldOperationException
{
    if( playerExists( id ) == false || gameExists( id ) == false ) {
        throw new IllegalArgumentException("Invalid player argument.");
    }
 
    // Get the specified field
    FieldState fieldstate = getEnemyBoardFieldState( id, coord );
 
    // Last but not at least, look if this field is unknown
    if( fieldstate == FieldState.UNKNOWN ) {
        // Now get the enemy board of this player
        EnemyBoard eBoard = boardSet_.get( id ).getEnemyBoard();
        // Set the mark
        eBoard.getField( coord ).setFieldState( FieldState.MARKED );
        // We have changed the data, notify observers.
        setChanged();
        notifyObservers( new ModelMessage( ModelMessage.MessageType.UPDATE ) );
        return true;
    }
 
    return false;
}

Im speziellen versendet das Model spezifizierte Nachrichten an seine Observer. Diese Nachrichten werden in der Klasse ModelMessage definiert. Das Model ist Thread-sicher und stellt synchronisierte Methoden bereit, die von den Spielern auch parallel aufgerufen werden können.

Die Klasse BattleshipModel hält desweiteren eine Instanz der Klasse BattleshipNode und leitet Änderungen im Knoten automatisch an seine Observer (zu dt. Beobachter) weiter. Das zu beobachtende Model beobachtet seinerseits die Klasse BattleshipNode. Dies ist auch der Grund, warum das Model zusätzlich das Interface Observer implementiert. Alle Netzwerkaktivitäten werden vom Model registriert. Dazu zählt auch der Empfang von neuen Nachrichten, die Aufnahme von neuen Peers oder die Entfernung von Teilnehmern aus dem Netzwerk.

/**
 * This model is an observable as well as an observer of another object.
 * In our case, this model will observe the network node. Any changes of the
 * node will be instantly dispatched to our observers.
 * 
 * @param o the observable object
 * @param arg   arguments, send by the observable
 */
@Override
public void update(Observable o, Object arg)
{
    setChanged();
    notifyObservers( new ModelMessage( ModelMessage.MessageType.NETWORKUPDATE ) );
}

Das Model stellt über das ModelInterface der Applikation alle wesentlichen Schnittstellen zur Verfügung, die für das Spiel »Schiffe versenken« benötigt werden. Dazu zählen auch Methoden der Netzwerkbibliothek, die vom Model gekapselt werden. Eine elementare Methode nennt sich connect und ist für die Verbindung zu anderen Knoten zuständig. Die Methode erzeugt einen neuen Netzwerkknoten, startet die Threads der Netzwerkbibliothek und registriert das Model als Beobachter bei der Netzwerkschicht.

/**
 * Connects to a battleship p2p network.
 *
 * @param id    the player id
 * @param host  destination host for bootstrapping
 * @param port  destination port for bootstrapping
 * @param bootstrap if true, client will try to bootstrap
 * @return  true, if connection was established
 */
@Override
public boolean connect(String id, String host, int port, boolean bootstrap)
{
    if( playerExists( id ) == false ) {
        throw new IllegalArgumentException("Invalid player argument.");
    }
 
    if( node_ != null && node_.connected() && !bootstrap )
        return true;
 
    if( node_ != null && node_.running() && bootstrap ) {
        return node_.buildNetwork( host, port, 30 );
    }
 
    boolean success = true;
 
    // Create the peer info
    PeerInfo info = new PeerInfo( "localhost", Integer.parseInt( getConfig().getPreferences().getPort() ) );
 
    info.setName( getPlayerName( id ) );
 
    int maxPeers = 99;  // This is a fixed size.
 
    node_ = new BattleshipNode( maxPeers, info );
 
    // Register our model as an Observer of the node
    node_.addObserver( this );
 
    // Init node
    node_.start();
 
    // Set the level for the network loggers
    Logging.setHandlersLevel( Logging.Type.NETWORK.getLoggerName(), Level.INFO );
 
    if( bootstrap ) {
        success = node_.buildNetwork( host, port, 30 );
    }
 
    return success;
}

Das Model stellt noch viele weitere Methoden zur Verfügung, die den Zugriff und die Manipulation der eigenen Daten kontrollieren. Es ist die zentrale Anlaufstelle für die gesamten Applikationsdaten.