wrp.pc

无线网络仿真工具Glomosim2.03

                            Init2(node,x,wrp->V[count].j);

                    /* Julian: for each x in N, x!=j, call Init2(j,x)
                     */
                    for (x=0; x<node->numNodes; x++)
                        if ((wrp->N[x]==1)&&(x!=wrp->V[count].j))
                            Init2(node,wrp->V[count].j,x);

                    /* tag(i)j <- null ; call DT
                     */
                    wrp->RTable[wrp->V[count].j].tag = 0;
                    DT(node, wrp->V[count], k);
                }
            }
            else
                /* tag(i)j <- null
                 */
                wrp->RTable[wrp->V[count].j].tag = 0;
        }
    }
    /* for each entry left, i != j
     */
    for (count=0; count<wrp->Vct; count++)
        if ((node->nodeAddr!=wrp->V[count].j)||(wrp->V[count].u==WRP_ACK)) {
            switch (wrp->V[count].u) {
            case WRP_UPDATE : {
                UpdList[ULct] = wrp->V[count];
                ULct++;
                break;
            }
            case WRP_ACK : {
               AckList[ALct] = wrp->V[count];
               ALct++;
               break;
            }
            default:
                for (i=0; i<wrp->Vct; i++)
                    printf("FAILURE on (%d,%d,%d,%d)\n",wrp->V[i].u,
                    wrp->V[i].j, wrp->V[i].RDkj, 
                    wrp->V[i].rpkj);
                printf("count = %d\n",count);
                assert(FALSE);
            }
        }
    if (ULct > 0)
        Update(node,UpdList,ULct,k);
    if (ALct > 0)
        ACK(node,AckList,ALct,k);

    pc_free(UpdList);
    pc_free(AckList);
    pc_free(response);
}

void DT(GlomoNode *node, const WrpTuple D, int k)
{
    GlomoRoutingWrp *wrp = (GlomoRoutingWrp *)node->appData.routingVar;
    int j, Dkj, pkj, b, count;
    
    j = D.j;
    Dkj = D.RDkj;
    pkj = D.rpkj;
    
    /* Julian: ERROR- if pkj is same as dest node, as in hello msg, problem
     */
    if (pkj==j)
        pkj = node->nodeAddr;

    /* Julian: MODIFICATION- if this node receives a message regarding
     *     a path to a destination, with a predecessor node which is a
     *     neighbor to this one, that conflicts with the message that
     *     said neighbor has previously sent, the update is invalid.
     *     Updates about paths thru active neighbors, should come from
     *     those neighbors first.
     */
    if (((wrp->Ni[pkj]==0) || (wrp->DTable[j].dat[pkj].dist<WRP_INFINITY) ||
        (k==pkj) || (NewNeighbor(node,pkj)))
        && ((pkj!=node->nodeAddr) || (wrp->Ni[j]==1))) {
        /* D(i)jk <- l(i)k + D(k)j ; p(i)jk <- p(k)j 
         */
#ifdef DEBUG
        printf("DT to %d via %d gets %d (link) + %d (entry)\n",j,k,
            wrp->LTable[k].dist,Dkj);
#endif
        wrp->DTable[j].dat[k].dist = wrp->LTable[k].dist + Dkj;
        wrp->DTable[j].dat[k].pred = pkj;
    
        /* for all neighbors b, Julian: b != k
         */
        for (b=0; b<node->numNodes; b++)
            if ( (b!=node->nodeAddr) && (wrp->Ni[b]==1) && (b!=k) ) {
                /* if k in path i-j in dist table thru neighb b
                 */
                if (wrp->DTable[j].dat[b].pred == k) {
                    /* D(i)jb <- D(i)kb + D(k)j ; p(i)jb <- p(k)j
                     */
                    wrp->DTable[j].dat[b].dist = wrp->DTable[k].dat[b].dist +
                        Dkj;
                    wrp->DTable[j].dat[b].pred = pkj;
                }
            }
    }
#ifdef DEBUG
    else
        printf("#%d: EXCLUDED (%d,%d,%d) from %d\n",node->nodeAddr,
            j,Dkj,pkj,k);
#endif
}

void Update(GlomoNode *node, const WrpTuple V[], int Vct, int k)
{
    int count, b, j;
    WrpTuple W;
    int *response = pc_malloc(sizeof(int)*node->numNodes);
    GlomoRoutingWrp *wrp = (GlomoRoutingWrp *)node->appData.routingVar;

#ifdef DEBUG
    printf("#%d: Update()\n",node->nodeAddr);
#endif
    assert(response);
    /* send ACK to neighbor k, Julian: only if response_list warrants
     */
    if (wrp->ACKthis==1) {
        W.u = WRP_ACK;
        W.j = k;
        W.RDkj = wrp->wpkt->hdr.seqNum;
        W.rpkj = node->nodeAddr;
        memset(response, 0, sizeof(int)*node->numNodes);
        addTuple(node,W,response);
    }
#ifdef DEBUG
    else
        printf("No Need to ACK this msg.\n");
#endif
    /* update <- 0; RTEMPi <- 0; DTEMPi for all b <- 0
     */
    
    /* for each triplet (j,D(k)j, p(k)j) in V(k,i), j != i do
     */
    for (count=0; count<Vct; count++)
        if (V[count].j!=node->nodeAddr) {
            DT(node,V[count],k);
        }
    for (count=0; count<Vct; count++) {
        j = V[count].j;
        for (b=0; b < node->numNodes; b++)
        {
            if ( (b==node->nodeAddr) || (wrp->Ni[b]==0) )
                continue;
            /* if there are b and j such that D(i)jb < D(i)j
             * or D(i)jb > D(i)j and b==succ(i)j 
             */
            if (wrp->DTable[j].dat[b].dist<wrp->RTable[j].dist)
            {
#ifdef DEBUG
                printf("#%d: Shorter path to %d found.\n",node->nodeAddr,j);
#endif
                RT_Update(node,j);
            }
            else if ((wrp->DTable[j].dat[b].dist > wrp->RTable[j].dist) &&
                      (b == wrp->RTable[j].succ))
            {
#ifdef DEBUG
                printf("#%d: Path to %j is now longer\n",node->nodeAddr,j);
#endif
                RT_Update(node,j);
            }
            else if ((b==wrp->RTable[j].succ)
                    &&(wrp->DTable[j].dat[b].pred
                    != wrp->RTable[j].pred))
            {
#ifdef DEBUG
                printf("#%d: Path to %j switched predecessor nodes\n",
                    node->nodeAddr);
#endif
                RT_Update(node,j);
            }
        }
    }
    pc_free(response);
}

static void ACK(GlomoNode *node, const WrpTuple V[], int Vct, int k)
{
    int count, b, j;
    GlomoRoutingWrp *wrp = (GlomoRoutingWrp *)node->appData.routingVar;

#ifdef DEBUG
    printf("#%d: ACK(V[],%d,%d)\n",node->nodeAddr,Vct,k);
#endif
    for (count=0; count < Vct; count++)
    {
#ifdef DEBUG
        printf("    seqno#%d from router %d\n",V[count].RDkj, V[count].rpkj);
#endif
        if (node->nodeAddr==V[count].j)
        {
            /* call Delete_RList(n); */
            Delete_RList(node,V[count].RDkj,V[count].rpkj);
        }
#ifdef DEBUG
        else
            printf("    Just overhearing ACK for another router.\n");
#endif
        /* RetransmissionCounter <- x */
    }
}

void RT_Update(GlomoNode *node, int j)
{
    int *response = pc_malloc(sizeof(int)*node->numNodes);
    WrpTuple W;
    GlomoRoutingWrp *wrp = (GlomoRoutingWrp *)node->appData.routingVar;
    int na, x, count, maxiter, i, do_rt_update;
    NODE_ADDR predecessor;
    int distance;

    assert(response);
    /* JJ */
    wrp->RTable[node->nodeAddr].tag = 1;

    /* find minimum of the distance entries DTmin
     */
    na = MinEntry(node,j);

    /* if D(i)js(i)j = DTmin, then na <- s(i)j
     */
/* OLD
    if ((wrp->RTable[j].succ >= 0) && 
        (wrp->DTable[j].dat[wrp->RTable[j].succ].dist == 
         wrp->DTable[j].dat[na].dist))
        na = wrp->RTable[j].succ;
*/
/* 6/26/99 */
    if (na > -1)
        distance = wrp->DTable[j].dat[na].dist;
    else
        distance = WRP_INFINITY;
    if ((wrp->RTable[j].succ >= 0) &&
        (wrp->DTable[j].dat[wrp->RTable[j].succ].dist ==
         distance))
        na = wrp->RTable[j].succ;
/***********/


    /* else na <- b |b in Ni and D(i)jb = DTmin
     * Julian: already done
     */

    /* x <- j
     */
    x = j;
    
    /* Julian: set maximum number of iterations to prevent infinite loop
     */
/* OLD
    maxiter = wrp->DTable[x].dat[na].dist + 2;
*/
/* 6/26/99 */
    if (na > -1)
        distance = wrp->DTable[x].dat[na].dist;
    else
        distance = WRP_INFINITY;
    maxiter = distance + 2;
/***********/


    /* while (D(i)xna = Min(D(i)xb for all b in Ni))
     *   and (D(i)xna < INFINITY and tag(i)x == NULL
     */
    if (na>-1) {
        while ((wrp->DTable[x].dat[na].dist
              == wrp->DTable[x].dat[MinEntry(node,x)].dist) &&
               (wrp->DTable[x].dat[na].dist < WRP_INFINITY) &&
               (wrp->RTable[x].tag == 0) && (maxiter > 0))
        {
            /* x <- p(i)xna
             */
            x = wrp->DTable[x].dat[na].pred;
            maxiter--;
#ifdef DEBUG
         printf("#%u: while loop x = %d\n",node->nodeAddr,x);
#endif

        }
        /* if p(i)xna == i or tag(i)x == correct
         * then tag(i)j = correct else tag(i)j = error
         */
/* OLD
        if ( ((wrp->DTable[x].dat[na].pred == node->nodeAddr)
              || (wrp->RTable[x].tag == 1))
            &&(wrp->DTable[x].dat[na].dist
              == wrp->DTable[x].dat[MinEntry(node,x)].dist))
            wrp->RTable[j].tag = 1;
        else
            wrp->RTable[j].tag = -1;
*/
        if ( (wrp->DTable[x].dat[na].pred == node->nodeAddr) ||
              (wrp->RTable[x].tag == 1))
            wrp->RTable[j].tag = 1;
        else
            wrp->RTable[j].tag = -1;

#ifdef DEBUG
        printf("TAG = %s\n",(wrp->RTable[j].tag == 1 ? "GOOD" : "BAD"));
#endif
    }
    if (wrp->RTable[j].tag == 1)
    {
        /* if D(i)j != DTmin or p(i)j != p(i)jna then */
/* OLD
        if ( (wrp->RTable[j].dist != wrp->DTable[j].dat[na].dist) ||
             (wrp->RTable[j].pred != wrp->DTable[j].dat[na].pred) )
*/
/* 6/26/99 */
        if (na > -1)
        {
            distance = wrp->DTable[j].dat[na].dist;
            predecessor = wrp->DTable[j].dat[na].pred;
        }
        else
        {
            distance = WRP_INFINITY;
            predecessor = -1;
        }
        if ( (wrp->RTable[j].dist != distance) ||
             (wrp->RTable[j].pred != predecessor) )
/***********/
        {
#ifdef DEBUG
            printf("#%u: Routing Table Entry for %d Changed.\n",
               node->nodeAddr,j);
#endif
            /* D(i)j <- DTmin; p(i)j <- p(i)jna ; s(i)j <- na */
/* OLD
            wrp->RTable[j].dist = wrp->DTable[j].dat[na].dist;
            wrp->RTable[j].pred = wrp->DTable[j].dat[na].pred;
            wrp->RTable[j].succ = na;
*/
/* 6/26/99 */
            wrp->RTable[j].dist = distance;
            wrp->RTable[j].pred = predecessor;
            wrp->RTable[j].succ = na;
/***********/

            /* Update Network Forwarding Table */
            NetworkUpdateForwardingTable(node, j, DEFAULT_INTERFACE, na);

            /* seqno <- seqno + 1 
             */
            wrp->LTable[wrp->RTable[j].succ].seqno++;
            /* add (0,j,DTmin,p(i)jna,seqno) to LISTi(x) for all x in Ni 
             */
            W.u = 0;
            W.j = j;
            W.RDkj = wrp->DTable[j].dat[na].dist;
            W.rpkj = wrp->DTable[j].dat[na].pred;
            for (count=0; count < node->numNodes; count++)
                if (wrp->Ni[count] == 1)
                    response[count] = 1;
                else
                    response[count] = 0;
            response[j] = 0;
            addTuple(node,W,response);
            for (count=0;count<node->numNodes;count++)
            {
                if ((count!=node->nodeAddr)&&(wrp->Ni[count]!=1)
                   &&(wrp->RTable[count].dist>=WRP_INFINITY))
                {
                    do_rt_update = 0;
                    for (i=0;i<node->numNodes;i++)
                        if ((i!=node->nodeAddr)&&(i!=count)&&(wrp->Ni[i]==1))
                        {
                            if (((wrp->DTable[count].dat[i].dist<WRP_INFINITY)
                               &&(wrp->DTable[count].dat[i].pred==j)) ||
                               (do_rt_update == 1))
                                do_rt_update = 1;
                            else
                                do_rt_update = 0;
                        }
                    if (do_rt_update==1)
                    {
#ifdef DEBUG
                        printf("#%d: Need RT_Update(%d)\n",node->nodeAddr,count);
#endif
                        wrp->RTable[count].tag = 0;
                        RT_Update(node,count);
                    }
                }
            }
        }
        else
        {
            /* D(i)j <- DTmin; p(i)j <- p(i)jna ; s(i)j <- na */
            wrp->RTable[j].dist = wrp->DTable[j].dat[na].dist;
            wrp->RTable[j].pred = wrp->DTable[j].dat[na].pred;
            wrp->RTable[j].succ = na;

            /* Update Network Forwarding Table */
            NetworkUpdateForwardingTable(node, j, DEFAULT_INTERFACE, na);
        }
    }
    else {
#ifdef DEBUG
        printf("#%d: No Path to %d\n",node->nodeAddr,j);
#endif
        /* if D(i)j < INF then begin */
        if (wrp->RTable[j].dist < WRP_INFINITY)
        {
            /* seqno <- seqno + 1 */
            /* add (0,j,INF,null,seqno) to LISTi(x) for all x in Ni */
            W.u = 0;
            W.j = j;
            W.RDkj = WRP_INFINITY;
            W.rpkj = -1;
            for (count=0; count<node->numNodes; count++)
                if (wrp->Ni[count]==1)
                    response[count]=1;
                else
                    response[count]=0;

            addTuple(node,W,response);
            /* call Clean_RList(seqno) */

            for (count=0; count < WRP_MAX_SEQ_NUM; count++)
                if (wrp->MRL[count].MRLsize > 0)
                    Delete_RList(node,count,j);
            /* call Create_RList(seqno) */
        }
        /* D(i)j <- INF ; p(i)j <- null ; s(i)j <- null */
        wrp->RTable[j].dist = WRP_INFINITY;
        wrp->RTable[j].pred = -1;