The packet sublayer in XUDP is responsible for bridging the gap between the parcel layer and the network layer. It is at this level that all flow control is accomplished and from where most of the CPU load will come. Duties include sending and receiving packets, retransmitting packets, acknowledging packets, adjusting round trip time statistics, dynamic congestion window sizing and insuring in-order delivery of packets on a per-parcel basis.
xudp_sendmsg attempts to transmit a packet to the next lower layer, currently via send through a UDP socket. Verifies quickly that the socket is available for writing, sends the packet and increments the total number of packets in the network. Command syntax is:
int xudp_sendmsg(struct XUDPCB *cb, struct XUDPPacket *pPacket);
1 int xudp_sendmsg(struct XUDPCB *cb, struct XUDPPacket *pPacket)
2 {
3 fd_set setFD;
4 struct timeval timestuff;
5
6 /** Some UNIX variants may require that the socket be checked for */
7 /** writeability IMMEDIATELY before writing to it. Here, select() */
8 /** is used to conduct a one-shot poll of the socket */
9
10 timestuff.tv_sec=0;
11 timestuff.tv_usec=0;
12 FD_ZERO(&setFD);
13 FD_SET(cb->fdCli, &setFD);
14 if (select((cb->fdCli+1), NULL, &setFD, NULL, ×tuff)<0)
15 xudpError("xudp_sendmsg");
16 if (FD_ISSET(cb->fdCli, &setFD))
17 {
Top of xudp_sendmsg function.
Lines 10-16 perform a poll using select to test whether the socket file descriptor is available for writing. Line 23 invokes send to write the payload of this packet to the socket. In this case, the connect function was previously used to inform the sockets layer of the endpoint's address, thereby allowing the use of send rather than sendto, even though a UDP socket is inherently connectionless.
18 /** Send the packet to the network. We're able to use send */
19 /** because we connect()ed the UDP sockets earlier, send() */
20 /** wraps around sendto(), but stores the connected endpoint's */
21 /** address to make it easy on us */
22
23 if (send(cb->fdCli, pPacket->payload, pPacket->length, 0)<0)
24 {
25 /** We've hit an error sending the packet. */
26 /** If the error is acceptable, just return a fail code, */
27
28 return -1;
29 }
30
31 cb->bytesSent+=pPacket->length;
32
33 }
34 else return -1;
35
36 return 0;
37 }
Bottom of xudp_sendmsg function.
xudp_recvmsg attempts to receive a packet from the next lower layer, currently via recv from a UDP socket. Function syntax is:
int xudp_recvmsg(struct XUDPCB *cb);
Operation of the function is similar to xudp_sendmsg, lines 12-19 testing if data is available to be read on the socket and line 25 reading in the payload with recv. Due to the prior connect function call, sockets automatically discards incoming packets from an address that differs from the set endpoint, and it is not important to use recvfrom.
Line 40 increments the count of the number of packets that it has received from the network, interpreted here as the number of packets XUDP believes have been placed in the network by the foreign host as of this time. packetsInPipeRmt can be used in determining whether to send an acknowledgement upon this value reaching the size of the local host's advertised window.
1 struct XUDPPacket *xudp_recvmsg(struct XUDPCB *cb)
2 {
3 struct XUDPPacket *pPacket;
4 int result;
5 fd_set setFD;
6 struct timeval timestuff;
7
8 /** Some UNIX variants may require that the socket be checked for */
9 /** readability IMMEDIATELY before reading from it. Here, select() */
10 /** is used to conduct a one-shot poll of the socket */
11
12 pPacket=NULL;
13 timestuff.tv_sec=0;
14 timestuff.tv_usec=0;
15 FD_ZERO(&setFD);
16 FD_SET(cb->fdCli, &setFD);
17 if (select((cb->fdCli+1), &setFD, NULL, NULL, ×tuff)<0)
18 xudpError("xudp_recvmsg");
19 if (FD_ISSET(cb->fdCli, &setFD))
20 {
21 /** Create an empty packet and recv() from the network into the */
22 /** payload. See xudp_sendmsg() for a discussion on connect() */
23
24 pPacket=makePacket();
25 if ((result=recv(cb->fdCli, pPacket->payload, cb->mps, 0))<=0)
26 {
27 /** We received nothing. Delete the packet we just */
28 /** made. */
29
30 deletePacket(pPacket);
31 pPacket=NULL;
32 }
33 else
34 {
35 /** Set up our packet's length field and increase our */
36 /** perceived number of packets in the network from the */
37 /** sending host */
38
39 pPacket->length=result;
40 cb->packetsInPipeRmt++;
41 }
42
43 }
44
45 return pPacket;
46 }
xudp_recvmsg function.
xudp_queueackwait queues up a recently sent packet on the ordered list of packets that comprise this packet's fragmented parcel where it will wait for an acknowledgement from the receiving end. Its syntax is:
int xudp_queueackwait(struct XUDPCB *cb, struct XUDPPacket *pPacket);
1 int xudp_queueackwait(struct XUDPCB *cb, struct XUDPPacket *pPacket)
2 {
3 struct XUDPFragParcel *pFragParcel;
4 struct XUDPPacket *pPacketTmp;
5 Boolean eflag=FALSE;
6
7 if (pPacket->next!=NULL)
8 pPacket->next->prev=pPacket->prev; /* Seperate packet from list */
9 if (pPacket->prev!=NULL)
10 pPacket->prev->next=pPacket->next; /* Without deleting it */
11 pPacket->next=NULL;
12 pPacket->prev=NULL;
13
14 /** Traverse list of parcels that have been wholly or partially */
15 /** sent to the network and are waiting for acknowledgements */
16
17 pFragParcel=cb->pAckWaitQueue->next;
18 while ((pFragParcel!=NULL)&&!eflag)
19 {
20 /** Descend list until we reach the end or the correct parcel */
21
22 if (pFragParcel->parcel!=pPacket->header.parcel)
23 pFragParcel=pFragParcel->next;
24
25 else eflag=TRUE;
26 }
Top of xudp_queueackwait function.
As it is likely that pPacket could be a member in a doubly-linked list, lines 7-12 prune the packet out of the list, redirecting the pointers of the previous and next nodes.
Lines 17-26 traverse through the list of packets waiting to receive acknowledgements, cb->pAckWaitQueue until the end of the list is reached (indicating this is the first packet in a new parcel) or the correct parcel is reached.
Potential Optimization: rather than traversing through linked lists as is the case here, creation of hash tables might reduce not only CPU load, but stack times as well!
If the end of the list was reached, lines 34-39 create a new fragmented parcel list taking relevant information from the packet's header. The packet is set at the head of the fragmented parcel's list of packets. Otherwise, the correct fragmented parcel was located and pFragParcel is left pointing at it.
Lines 47-57 verify that the packet is not already in the queue, as would happen with a packet that has been retransmitted. Line 67 deletes the packet under this condition. Line 62 adds the packet to the end of the queue, if it isn't in it already. Since this is the sending side, we are assured that packets are in order, as they are being sent that way, so no insertion mechanism is necessary.
28 if (pFragParcel==NULL) /* New parcel */
29 {
30 /** There weren't any references to this parcel number in the */
31 /** ACK Wait list, so we'll create a new parcel and tack it */
32 /** onto the end of the list */
33
34 pFragParcel=makeFragParcel();
35 pFragParcel->parcel=pPacket->header.parcel;
36 pFragParcel->options=pPacket->header.options;
37 pFragParcel->tto=pPacket->header.tto;
38 pFragParcel->headPacket=pPacket;
39 addFragParcel(cb->pAckWaitQueue, pFragParcel);
40 }
41 else
42 {
43 /** Make sure the packet isn't already in the queue, (i.e. its a */
44 /** retransmit) */
45
46 /** Traverse the list of packets that form the parcel */
47 pPacketTmp=pFragParcel->headPacket;
48 eflag=FALSE;
49 while ((pPacketTmp!=NULL) && !eflag)
50 {
51 /** If the sequence number of this packet matches ours, jump out */
52 /** immediately, setting eflag */
53
54 if (pPacketTmp->header.sequence==pPacket->header.sequence)
55 eflag=TRUE;
56 else pPacketTmp=pPacketTmp->next;
57 }
58
59 if (!eflag)
60 {
61 /** Add the packet to the end of the queue. */
62 addPacket(pFragParcel->headPacket, pPacket);
63 }
64 else
65 {
66 /** Packet was a retransmit copy, blow it away. */
67 deletePacket(pPacket);
68 }
69 }
70
71 return 0;
72 }
Bottom of xudp_queueackwait function.
xudp_organizeincoming queues up incoming packets on their appropriate fragmented parcel's packet queue, insuring in-order delivery.
int xudp_organizeincoming(struct XUDPCB *cb);
The first fifty lines of code are nearly identical to those in xudp_queueackwait: pruning the packet out of the incoming queue, locating its parcel on the receive queue, creating a new parcel when the first packet in that parcel arrives. This purposefully mimics the sending side operation on the receiving side. If this was in fact a new parcel creation, this function stops there.
1 int xudp_organizeincoming(struct XUDPCB *cb)
2 {
3 struct XUDPFragParcel *pFragParcel;
4 struct XUDPPacket *pPacket, *pPacketTmp, *pPacketSearch;
5 Boolean eflag=FALSE;
6
7 /** Traverse the list of packets received from the network but not */
8 /** ordered and placed under fragmented parcels */
9
10 pPacket=cb->pRecvQueue->next;
11 while (pPacket!=NULL)
12 {
13 pPacketTmp=pPacket->next;
14
15 /** Seperate the packet from the list without deleting it */
16
17 if (pPacket->next!=NULL)
18 pPacket->next->prev=pPacket->prev;
19 if (pPacket->prev!=NULL)
20 pPacket->prev->next=pPacket->next;
21 pPacket->next=NULL;
22 pPacket->prev=NULL;
23
24 /** Traverse the list of parcels coming in from the network */
25
26 pFragParcel=cb->pRecvWaitQueue->next;
27 eflag=FALSE;
28 while ((pFragParcel!=NULL)&&!eflag)
29 {
30 /** Descend list until we reach the end or the correct */
31 /** parcel */
32
33 if (pFragParcel->parcel!=pPacket->header.parcel)
34 pFragParcel=pFragParcel->next;
35 else eflag=TRUE;
36 }
37 if (pFragParcel==NULL) /* New parcel */
38 {
39 /** No reference was made to this parcel number in the */
40 /** list, so we're going to make a new parcel and tack */
41 /** it on the end of the list */
42
43 pFragParcel=makeFragParcel();
44 pFragParcel->parcel=pPacket->header.parcel;
45 pFragParcel->options=pPacket->header.options;
46 pFragParcel->tto=pPacket->header.tto;
47 pFragParcel->headPacket=pPacket;
48 addFragParcel(cb->pRecvWaitQueue, pFragParcel);
49 }
Top of xudp_organizeincoming function.
The code below is reached when the correct parcel is found. This is XUDP's in-order delivery mechanism. Lines 58-70 form a search loop that exits under two conditions: first, if the loop arrives at the end of the queue, second, if the packet currently being placed has a sequence number lesser than the packet the algorithm is examining in the list. The second condition is sufficient to insure that the list orders itself as it is being built.
50 else
51 {
52 /** Search list of packets in parcel and insert in the */
53 /** appropriate place, ordering the packets by */
54 /** ascending sequence number */
55
56 /*** Traverse the list of packets that form this parcel */
57
58 pPacketSearch=pFragParcel->headPacket;
59 eflag=FALSE;
60 while ((pPacketSearch!=NULL)&&!eflag)
61 {
62 /** Bail out if the sequence number of our packet */
63 /** is ever less than that of the current list */
64 /** entry or we reach the end of the list */
65
66 if (pPacketSearch->header.sequence <
67 pPacket->header.sequence)
68 pPacketSearch=pPacketSearch->next;
69 else eflag=TRUE;
70 }
Lines 50-70 of the xudp_organizeincoming function.
Lines 71-77 handle the case when the end of the list of packets is reached and the new packet's sequence number is still higher - the packet should fall at the end of the current queue. Line 76 adds the packet to the end of the queue.
Two cases remain and are handled in lines 83-95. If the packet's sequence number numerically places it at the head of the list, line 93 takes the entire list and adds it to the back of the new packet, then line 94 sets the packet as the head of the list. Lines 83-84 remain to insert the packet between its lower and upper sequence number neighbors.
71 if (pPacketSearch==NULL)
72 {
73 /** We're at the end of the list, so just put the */
74 /** packet there */
75
76 addPacket(pFragParcel->headPacket, pPacket);
77 }
78 else
79 {
80 /** We need to insert the packet between this list */
81 /** member and the previous */
82
83 if (pPacketSearch->prev!=NULL)
84 insertPacket(pPacketSearch->prev, pPacket);
85 else
86 {
87 /** This packet comes before every other one */
88 /** Insert the packet at the beginning of the */
89 /** list Add current list of packets in parcel */
90 /** to the end of our single packet and set */
91 /** parcel to start on that packet. */
92
93 addPacket(pPacket, pFragParcel->headPacket);
94 pFragParcel->headPacket=pPacket;
95 }
96
97 }
98 }
99 pPacket=pPacketTmp;
100 }
101
102 return 0;
103 }
Bottom of thexudp_organizeincoming function.
xudp_xmit dequeues packets waiting in the outgoing packet queue, assembles their transmittable headers in the packet payload and transmits the packets through xudp_sendmsg.
int xudp_xmit(struct XUDPCB *cb);
xudp_xmit Acts primarily as an interface to the xudp_send function. Lines 10-13 instruct the loop to grab packets from the list of packets waiting to be sent to the network. Lines 19-42 prepare the header for transport in the payload, creating the header exactly as seen in figure 7.1.
evidenced by the comments on lines 15-17, I'm still doubtful that this is the best way to generate a header of this sort. But, with byte ordering and alignment varying from machine to machine, this may in fact be the only way. This area needs optimization.
1 int xudp_xmit(struct XUDPCB *cb)
2 {
3 struct XUDPPacket *pPacket, *pPacketTmp;
4 char *payload;
5 u_short temp;
6 u_int tempint;
7
8 /** Traverse the list of packets waiting to be transmitted */
9
10 pPacket=cb->pXmitQueue->next;
11 while (pPacket!=NULL)
12 {
13 pPacketTmp=pPacket->next;
14
15 /** WARNING!!!!! NOTE, THIS is SLOW, dumb code. */
16 /** Although it looks like it, this will not work for */
17 /** different typesizes than the default! */
18
19 payload=pPacket->payload;
20 *(payload++)=pPacket->header.options;
21 *(payload++)=pPacket->header.cmds;
22 temp=htons(pPacket->header.window);
23 memcpy(payload, &temp, 2);
24 payload+=2;
25
26 tempint=htonl(pPacket->header.timestamp);
27 memcpy(payload, &tempint, 4);
28 payload+=4;
29 tempint=htonl(pPacket->header.tto);
30 memcpy(payload, &tempint, 4);
31 payload+=4;
32
33 temp=htons(pPacket->header.sequence);
34 memcpy(payload, &temp, 2);
35 payload+=2;
36 temp=htons(pPacket->header.parcel);
37 memcpy(payload, &temp, 2);
38 payload+=2;
39
40 temp=htons(pPacket->header.length);
41 memcpy(payload, &temp, 2);
42 payload+=2;
43
Top of xudp_xmit function.
The remaining portion of xudp_xmit handles sending the packet (line 46) and subsequently queueing it on the list of packets waiting to receive acknowledgements with xudp_queueackwait. It will not attempt to queue a packet with a time to obsolescence of zero, as that packet is a one shot and can never be retransmitted.
44 /** Send the packet */
45
46 if (xudp_sendmsg(cb, pPacket)>=0)
47 {
48 if (pPacket->header.tto)
49 {
50 /** Queue up the packet to wait for an acknowledgement */
51
52 xudp_queueackwait(cb, pPacket);
53 pPacket=pPacketTmp;
54 }
55 else
56 {
57 /** Delete packet if it's a ONESHOT */
58
59 deletePacket(pPacket);
60 pPacket=pPacketTmp;
61 }
62
63 } else pPacket=NULL;
64
65 }
66 return 0;
67 }
Bottom of xudp_xmit function.
xudp_recv receives a packet incoming from the network, making use of the xudp_recvmsg function, and fills out a struct XUDPPacket with the appropriate payload and header information, insuring that the packet delivered to the XUDP protocol stack is in the correct form.
int xudp_recv(struct XUDPCB *cb);
The function is necessarily complicated due to the undetermined length of the optional commands present in the packet header as well as the chance that the packet received could be a retransmitted duplicate. Below, the functionality is enumerated:
1 int xudp_recv(struct XUDPCB *cb)
2 {
3 struct XUDPFragParcel *pFragParcel;
4 struct XUDPPacket *pPacket, *pPacketTmp;
5 struct XUDPCmd *pCmd;
6 char *payload, cmd;
7 u_short temp;
8 u_int tempint;
9 int i=0;
10 Boolean eflag;
11
12 /** Attempt to receive packets from the network. Continue doing so */
13 /** until unsuccessful. */
14
15 while ((pPacket=xudp_recvmsg(cb))!=NULL)
16 {
17 i++;
18
19 /** WARNING!!!! */
20 /** Although it looks like it, this will not work for */
21 /** different typesizes than the default! */
22
23 payload=pPacket->payload;
24 pPacket->header.options=*(payload++);
25 pPacket->header.cmds=*(payload++);
26 memcpy(&temp, payload, 2);
27 pPacket->header.window=ntohs(temp);
28
29 payload+=2;
30 memcpy(&tempint, payload, 4);
31 pPacket->header.timestamp=ntohl(tempint);
32 payload+=4;
33 memcpy(&tempint, payload, 4);
34 pPacket->header.tto=ntohl(tempint);
35
36 payload+=4;
37 memcpy(&temp, payload, 2);
38 pPacket->header.sequence=ntohs(temp);
39 payload+=2;
40 memcpy(&temp, payload, 2);
41 pPacket->header.parcel=ntohs(temp);
42
43 payload+=2;
44 memcpy(&temp, payload, 2);
45 pPacket->header.length=ntohs(temp);
46
47 payload+=2;
Top of xudp_recv function, reassembling the packet's header structure.
Lines 1-47 receive a packet from the network with xudp_recvmsg and move through the packet payload, reassembling the header one element at a time, accounting for network-byte-ordered integers.
Below, lines 48-79 constitute part 1 of the duplication detection process, examining the queue of received fragmented parcels. The searching algorithm consists of two nested while loops: an external loop that traverses through the queue of parcels until either the parcel that matches this packet's parcel is found, or the end of the queue is reached and an internal loop that descends the list of packets in that parcel, exiting upon detecting a matching packet sequence number or reaching the end of the list.
If at any point in this routine or the following routines, eflag gets set, the packet has been determined to be a duplicate.
48 /*** Find out NOW if we've received a duplicate packet. We've */
49 /*** got to go through both the immediate packet-level receive */
50 /*** queue as well as the fragmented parvel recv-wait queue */
51
52 /** Traverse list of received, fragmented parcels */
53
54 pFragParcel=cb->pRecvWaitQueue->next;
55 eflag=FALSE;
56 while ((pFragParcel!=NULL)&&(!eflag))
57 {
58 /** See if we're on the right parcel */
59
60 if (pFragParcel->parcel==pPacket->header.parcel)
61 {
62 /** Traverse list of packets that form the fragmented */
63 /** parcel */
64
65 pPacketTmp=pFragParcel->headPacket;
66 while ((pPacketTmp!=NULL)&&(!eflag))
67 {
68 /** If we find a match for the sequence number of */
69 /** the packet, mark eflag as true (we have a */
70 /** dupe) */
71
72 if (pPacket->header.sequence ==
73 pPacketTmp->header.sequence) eflag=TRUE;
74 pPacketTmp=pPacketTmp->next;
75 }
76
77 }
78 pFragParcel=pFragParcel->next;
79 }
xudp_recv function, detecting duplicate packets in the received parcel queue.
Lines 80-84 handle the second characteristic of a duplicate packet, one that is a member of a parcel that has already been completely received and reassembled, and therefore isn't present in the queue of received, fragmented parcels. usedparcels[] is a simple Boolean array that is updated in xudp_reassembleparcel by setting the array element that is equal to the parcel's sequence number to a nonzero value.
80 81 /** If the packet belongs to a parcel that we've already */ 82 /** reassembled, then it's a delayed duplicate and we'll get rid */ 83 /** of it */ 84 if (cb->usedparcels[pPacket->header.parcel]) eflag=TRUE;
xudp_recv function, detecting duplicate packet by virtue of its parcel having been entirely received and reassembled.
The section below (85-104) detects duplicate packets in the queue of received packets. It follows a similar format to before, setting eflag if it matches both packet sequence numbers and parcel sequence numbers.
85
86 /** Do unless we already have detected a duplicate packet */
87
88 if (!eflag)
89 {
90 /** Traverse list of received packets */
91
92 pPacketTmp=cb->pRecvQueue->next;
93 while ((pPacketTmp!=NULL) && (!eflag))
94 {
95 /** If both the parcel and sequence numbers match, we */
96 /** have a dupe. */
97 if ((pPacketTmp->header.parcel ==
98 pPacket->header.parcel) &&
99 (pPacketTmp->header.sequence ==
100 pPacket->header.sequence)) eflag=TRUE;
101 pPacketTmp=pPacketTmp->next;
102 }
103
104 }
xudp_recv function, detecting duplicates in the received packets queue.
Lines 105-179 wrap up the xudp_recv function, primarily stripping the variable length commands out of the payload unless the packet has been determined to be a duplicate (eflag is set) line 108 deletes it and the rest of the function is skipped.
First, the receiver's advertised window is updated to that contained in the packet header (line 114.)
The while loop from line 118 to line 166 executes while commands remain to be processed in the payload immediately following the packet's header. Figure 7.2 displays the organization of the commands stored in the payload; the size and number of arguments to each command depend on the command itself. The loop uses the payload character pointer to maintain the current position in the payload buffer.
Currently, five commands are defined, table 7.1 contains the command names as well as the size of the argument buffer.
| Command | Arguments |
| C_ACK | 4 bytes |
| C_EOP | no arguments |
| C_ACKPARCEL | 2 bytes |
| C_ACKCMDPCL | 2 bytes |
| C_CLOSE | no arguments |
The processed commands are stored in struct XUDPCmd structures, as described in chapter 7.2. Line 164 adds the command onto the end of the incoming command queue.
Once the packet has been appropriately handled, line 173 adds the packet to the end of the queue of received packets ( cb->pRecvQueue) and line 174 increases our the number of packets we perceive that the remote host has sent to the network.
105 /** Delete the packet if it is a duplicate or else continue */
106 /** normal unwrapping. */
107
108 if (eflag) deletePacket(pPacket);
109 else
110 {
111 /** Set the control block's Remote Window size to the */
112 /** Advertised Window of this packet */
113
114 cb->winRemote=pPacket->header.window;
115
116 /** Strip all of the commands out of the header */
117
118 while(pPacket->header.cmds)
119 {
120 /** We're using "payload" to point at the current */
121 /** position in the payload of the packet */
122
123 cmd=*payload;
124 payload++;
125 pCmd=makeCmd();
126 pCmd->cmd=cmd;
127
128 switch(cmd)
129 {
130 case C_ACK:
131 pCmd->length=sizeof(Sequence)*2;
132 memcpy(pCmd->argbuffer, payload, pCmd->length);
133 payload+=pCmd->length;
134 break;
135 case C_ACKPARCEL:
136 pCmd->length=sizeof(Sequence);
137 memcpy(pCmd->argbuffer, payload, pCmd->length);
138 payload+=pCmd->length;
139 break;
140 case C_EOP:
141 pCmd->length=sizeof(Sequence)*2;
142 memcpy(pCmd->argbuffer, &(pPacket->header.parcel),
143 sizeof(Sequence));
144 memcpy(pCmd->argbuffer+sizeof(Sequence),
145 &(pPacket->header.sequence), sizeof(Sequence));
146 break;
147 case C_ACKCMDPCL:
148 pCmd->cmd=C_ACKPARCEL; /* Treat as if regular parcel */
149 pCmd->length=sizeof(Sequence);
150 memcpy(pCmd->argbuffer, payload, pCmd->length);
151 payload+=pCmd->length;
152 break;
153 case C_CLOSE:
154 deleteCmd(pCmd);
155 pCmd=NULL;
156 cb->state=XUDP_CLOSE_WAIT;
157 cb->closing=makeTimestamp();
158 break;
159 default: break;
160 }
161
162 /** Queue the commands on the list of incoming commands */
163
164 if (pCmd!=NULL) addCmd(cb->pCmdInQueue, pCmd);
165 pPacket->header.cmds--;
166 }
167
168 if (pPacket->header.length)
169 memmove(pPacket->payload, payload, pPacket->header.length);
170
171 /** Queue packet on list of received packets */
172
173 addPacket(cb->pRecvQueue, pPacket);
174 cb->packetsInPipeRmt++;
175
176 }
177 }
178 return i;
179 }
Bottom of xudp_recv function.
xudp_recvackpackets wades through the queue of incoming commands and interprets C_ACK commands - received acknowledgements of packets sent by the local host. It sets ack on the acknowledged packets waiting on the queue of fragmented parcels waiting for acknowledgements.
int xudp_recvackpackets(struct XUDPCB *cb);
The function consists of a while loop that searches through the list of incoming commands (pCmdInQueue) invoking the code within the if statment on line 18 when a command is a C_ACK.
Lines 20-24 parse the argument buffer as two network-byte-ordered 16-bit unsigned integers; the first is the number of the parcel, the second the packet sequence number.
Lines 26-33 constitute a loop structure that attempts to locate the fragmented parcel in pAckWaitQueue with a matching parcel sequence number. The loop exits with pFragParcel pointing to the parcel and eflag set, or pFragParcel = NULL, indicating that the end was reached without a match.
1 int xudp_recvackpackets(struct XUDPCB *cb)
2 {
3 struct XUDPCmd *pCmd, *pCmdTmp;
4 struct XUDPFragParcel *pFragParcel;
5 struct XUDPPacket *pPacket;
6 Sequence sequence, parcel, temp;
7 Timestamp ts, maxrtt=0;
8 Boolean eflag=FALSE, anyacks=FALSE;
9
10
11 /** Traverse list of incoming commands */
12
13 pCmd=cb->pCmdInQueue->next;
14 while (pCmd!=NULL)
15 {
16 pCmdTmp=pCmd->next;
17
18 if (pCmd->cmd==C_ACK)
19 {
20 memcpy(&temp, pCmd->argbuffer, sizeof(Sequence));
21 parcel=ntohs(temp);
22 memcpy(&temp, (pCmd->argbuffer)+sizeof(Sequence),
23 sizeof(Sequence));
24 sequence=ntohs(temp);
25
26 pFragParcel=cb->pAckWaitQueue->next;
27 eflag=FALSE;
28 while((pFragParcel!=NULL)&&!eflag)
29 {
30 if (pFragParcel->parcel!=parcel)
31 pFragParcel=pFragParcel->next;
32 else eflag=TRUE;
33 }
Top of the xudp_recvackpackets function.
Lines 35-58 are executed if pFragParcel is non-null, pointing to the matched fragmented parcel. Lines 36-43 attempt to locate within the queue of packets that comprise the fragmented parcel a packet that matches the acknowledged packet sequence number. On success, pPacket points at the packet and eflag is set; on failure, pPacket = NULL.
Lines 47-55 are executed if the acknowledged packet is indeed found. The following tasks are accomplished:
34 if (pFragParcel!=NULL)
35 {
36 pPacket=pFragParcel->headPacket;
37 eflag=FALSE;
38 while((pPacket!=NULL)&&!eflag)
39 {
40 if (pPacket->header.sequence!=sequence)
41 pPacket=pPacket->next;
42 else eflag=TRUE;
43 }
44
45 if (pPacket!=NULL)
46 {
47 anyacks=TRUE;
48 pPacket->ack=TRUE;
49 deleteCmd(pCmd);
50 if (cb->packetsInPipe>0) cb->packetsInPipe--;
51 cb->bytesACKed=cb->bytesACKed+pPacket->length;
52 ts=makeTimestamp();
53 cb->timeElapsed=ts;
54 cb->rtt=ts-pPacket->header.timestamp;
55 xudp_rttmath(cb);
56 }
57
58 }
59 }
60 pCmd=pCmdTmp;
61 }
62
63 return 0;
64 }
Bottom of the xudp_recvackpackets function.
xudp_ackpackets creates acknowledgement commands on the outgoing command queue (cb->pCmdQueue) for packets that comprise the queue of fragmented parcels that have been received from the network that haven't generated an acknowledgement yet.
int xudp_ackpackets(struct XUDPCB *cb);
1 int xudp_ackpackets(struct XUDPCB *cb)
2 {
3 struct XUDPCmd *pCmd;
4 struct XUDPFragParcel *pFragParcel;
5 struct XUDPPacket *pPacket;
6 Sequence sequence;
7
8 pFragParcel=cb->pRecvWaitQueue->next;
9
10 /*** Generate ACKs for each packet */
11
12 while (pFragParcel!=NULL)
13 {
14 if (!pFragParcel->ack)
15 {
16 pPacket=pFragParcel->headPacket;
17 while (pPacket!=NULL)
18 {
19 if (!pPacket->ack)
20 {
21 pCmd=makeCmd();
22 pCmd->cmd=C_ACK;
23 pCmd->length=2*sizeof(Sequence);
24 sequence=htons(pPacket->header.parcel);
25 memcpy(pCmd->argbuffer, &sequence,
26 sizeof(Sequence));
27 sequence=htons(pPacket->header.sequence);
28 memcpy(pCmd->argbuffer+sizeof(Sequence),
29 &sequence, sizeof(Sequence));
30 addCmd(cb->pCmdQueue, pCmd);
31 pPacket->ack=TRUE;
32 if (cb->packetsInPipeRmt>0) cb->packetsInPipeRmt--;
33 }
34 pPacket=pPacket->next;
35
36 }
37 }
38 pFragParcel=pFragParcel->next;
39 }
40
41 return 0;
42 }
xudp_ackpackets function.
Lines 12-39 are a while loop that traverses through the list of fragmented parcels on the receive wait queue until the end of the queue is reached. Inside, lines 16-37 are executed if the fragmented parcel hasn't already been acknowledged in its entirety.
A similar loop to find unacknowledged packets exists inside this loop over lines 16-36. If an unacknowledged packet is found, lines 21-29 create a new struct XUDPCmd, initializing it as a C_ACK command, with a four byte argument buffer consisting of two network-byte-ordered 16-bit unsigned integers: the parcel number and sequence number, respectively. Line 30 adds the command to the end of the outgoing commands queue ( cb->pCmdQueue.) Line 31 marks this packet as having generated an acknowledgement. Line 32 decreases the number of packets perceived by the local host to have been placed in the network by the remote host.
xudp_retransmit tromps through the queue of fragmented parcels waiting for acknowledgement, examining the packets that form them. If it detects that a packet has exceeded the Retransmission Time Out timer (RTO), it queues that packet up for retransmission.
int xudp_retransmit(struct XUDPCB *cb);
1 int xudp_retransmit(struct XUDPCB *cb)
2 {
3 struct XUDPPacket *pPacket, *pPacketTmp, *pPacketNew;
4 struct XUDPFragParcel *pFragParcel;
5 Timestamp ts;
6
7 ts=makeTimestamp();
8
9 /** Traverse the list of fragmented parcels waiting to be */
10 /** acknowledged */
11
12 pFragParcel=cb->pAckWaitQueue->next;
13 while(pFragParcel!=NULL)
14 {
15 /** Traverse the list of packets that form this parcel that */
16 /** are waiting to be acknowledged. */
17
18 pPacket=pFragParcel->headPacket;
19 while(pPacket!=NULL)
20 {
21 pPacketTmp=pPacket->next;
22
23 /** Only consider the packets that haven't been */
24 /** acknowledged yet */
25
26 if (!(pPacket->ack))
27 {
xudp_ackpackets function.
28 /** See if we've exceeded the RTO */
29
30 if ((ts-pPacket->header.timestamp)>=cb->rto)
31 {
32 /** Packet needs to be retransmit. */
33 /** Put a new timestamp in */
34
35 pPacket->header.timestamp=ts;
36
37 /** Create a copy to be queued up for transmission, but */
38 /** castrate the copy so it's not pointing at this queue */
39
40 pPacketNew=makePacket();
41 memcpy((void *)pPacketNew, (void *)pPacket,
42 sizeof(struct XUDPPacket));
43 pPacketNew->next=NULL;
44 pPacketNew->prev=NULL;
45
46 /** Insert it at the head of the outgoing packets */
47 /** queue. It will be sent and requeued on the */
48 /** Acknowledgement Wait queue. We're not creating */
49 /** a new packet here, just retransmitting an old */
50 /** one. **No need to adjust the packetsInPipe */
51 /** counter because we assume the packet has left the */
52 /** network, and we're just going to put it back in.***/
53
54 insertPacket(cb->pXmitQueue, pPacketNew);
55
56 /** Increase RTO exponentially, RTO will only get */
57 /** set by the _rttmath algorithm, so we'll keep */
58 /** backing off until we ACK something. */
59
60 cb->rto=cb->rto<<1;
61 }
62 }
63 pPacket=pPacketTmp;
64 }
65 pFragParcel=pFragParcel->next;
66 }
67 return 0;
68 }
xudp_ackpackets function.
int xudp_rttmath(struct XUDPCB *cb);
int xudp_rttmath(struct XUDPCB *cb)
{
float error;
/** Retransmit Time Out timer calculations, straight out of */
/** _Congestion Avoidance and Control_ */
/*** The error between the measured RTT and the average */
error=((float)cb->rtt)-(cb->rttavg);
/*** Calculate the new average taking into account a bit of the */
/*** error */
cb->rttavg+=(RTTGAIN*error);
/*** Calculate the variance of the RTT estimation */
if (error<0) error=-error;
cb->rttvar+=RTTGAIN*(error-(cb->rttvar));
/*** RTO is average RTT plus four times the variance */
cb->rto=(int)(cb->rttavg+4*cb->rttvar);
cb->bandwidth=(cb->bytesACKed*1000)/(cb->timeElapsed);
if (cb->rtt > cb->rttmax) cb->rttmax=cb->rtt;
if (cb->rtt < cb->rttmin) cb->rttmin=cb->rtt;
cb->rttmax-=0.01*(cb->rttmax-cb->rttavg);
cb->rttmin+=0.01*(cb->rttavg-cb->rttmin);
xudp_windowchange(cb);
return 0;
}
xudp_ackpackets function.
int xudp_rttmath(struct XUDPCB *cb);
int xudp_windowchange(struct XUDPCB *cb)
{
if (cb->state==XUDP_SOFT_START)
{
if ((float)cb->rtt > cb->rttavg+(0.1*cb->rttavg))
cb->state=XUDP_CONG_ANTICIPATION;
/* cb->windowdelta+=WINDSTEP;*/
cb->windowdelta=0.25;
}
if (cb->state==XUDP_CONG_ANTICIPATION)
{
if ((float)cb->rtt < ((cb->rttmin+cb->rttmax)/2))
cb->state=XUDP_NORMAL;
cb->windowdelta=-1;
}
if (cb->state==XUDP_NORMAL)
{
if ((float)cb->rtt > ((cb->rttmin+cb->rttmax)/2))
cb->state=XUDP_CONG_ANTICIPATION;
/* cb->windowdelta+=WINDSTEP;*/
cb->windowdelta=0.125;
}
/** Our congestion window is the minimum of the max Remote */
/** advertised window size and the current window adjusted by */
/** windowdelta, but always at least 1. */
if (cb->windowdelta>MAXWIND) cb->windowdelta=MAXWIND;
if (cb->windowdelta<-MAXWIND) cb->windowdelta=-MAXWIND;
cb->winFCongestion+=cb->windowdelta;
if (cb->winFCongestion>(float)cb->winRemote)
cb->winFCongestion=(float)cb->winRemote;
if (cb->winFCongestion<1.0) cb->winFCongestion=1.0;
cb->winCongestion=(int)cb->winFCongestion;
cb->winCongestion=1;
return 0;
}
xudp_ackpackets function.