Transition probability matrix generation:

1. convert timestamp to serial number and then sort
   
2. divide area into grids
   
3. loop: for each taxiid, find current grid & next grid, fill into grid matrix (row is current grid #, column is next grid #)
   
4. get probability matrix by normalizing grid matrix

---

Update generation:

1. set parameters, such as time period (1 day / 1440 mins), GUID (from 1 to 4000), grid number, longitude and latitude range
   
2. initialize the taxi matrix ( GUID | current grid | timestamp), assign current grid according to location matrix which keeps density information about the taxi location, set timestamp to 0
   
3. in every min (timestamp + 1), check every GUID whether it generates update
   
4. compute destination grid number through transition probability matrix (convert to probability CDF matrix); if it is different from source grid number, then generate an update
   
5. write | event type | GUID | source | destination | timestamp | into output file
   

---

table TAXIDATA has all data loaded, table TAXI1 loads only the first data file

table contents are as below
CREATE TABLE TAXIDATA
(
ID NUMBER(10) CONSTRAINT TAXIDATA_ID NOT NULL,
TAXIID NUMBER(7),
LONGITUDE NUMBER(9,6),
LATITUDE NUMBER(8,6),
SPEED NUMBER(3),
ANGLE NUMBER(3),
DATETIME TIMESTAMP(6),
STATUS NUMBER(1),
EXTENDSTATUS NUMBER(1),
REVISED NUMBER(1),
PRIMARY KEY(ID) )
TABLESPACE USERS;

---

The picture shows 10k entries chosen from the first data file. The covered area is longitude from 121.2 to 121.8 and latitude from 31 to 31.5. The area is divided into 10*10 grids, which is 100 grids in total.

---

Discussion:

1. model traffic and speed
   
2. network topology layout
   
3. integrate update and query generation; GNRS performance evalution
   

---

Modeling steps:
1.initialize grids: each grid has a GNRS server, distribute taxies according to location matrix from SUVNet, insert mapping information into GNRS servers (K copies, including local GNRS server and K-1 servers in other grids).
2.generate updates list(according to transition probability matrix) and lookups list(according to modified zipf law), updates and lookups are interleaved in an ascending order of timestamp.
3.update: each update has K copies, one stored in local GNRS, other K-1 copies stored in other GNRS servers which is decided by hash function. Update latency is the distance between local grid and farthest grid of K-1 servers.
4.lookup: hash GUID at local GNRS server, lookup latency is the distance between local grid and nearest grid of K servers.
5.examine each update/lookup in the order of timestamp, calculate average update/lookup latency.

6. application example: multimedia on demand system, peer-to-peer (texting/call) communication
   

(1) multimedia on demand system:

Node A sends a query to local GNRS server for service provider B's GUID; GNRS server returns B's network address; A sends service request to B; B sends media file of size x MB (chunked into k packets)to A, A acknowledge each packet received successfully; A moves to another grid (based on transition probability matrix) during the media file transmission, B fails to receive ACK during to A's change of network address; B queries its local GNRS server for A's network address, if B finds A's network address updated, it sends packets to the new address.

Data to be measured: update / query latency due to A's moving during the media file transmission

(2) peer-to-peer commnuication

Node A and B are mobile nodes. There is a packet flow between A and B. Measure the update / query delay due to their movements.

---

Simulation designs:

1. Initialization
   

(1) Topology

--- Grid setting, e.g. 5 by 5;
--- Infrastructure setting, includes GNRS server, Base station, router. Assume each grid has one GNRS server, one BS, one router. Also assume full connectivity.
--- Device deployment: mobile nodes deployment follow location matrix from SUVNet.
--- Routing strategy for mobile client - static server and mobile client - mobile client communication pattern.

(2) Parameter list

--- Lookup latency
--- Update latency
--- Routing latency (distribution)
--- Application related parameters: file size distribution for multimedia on demand application and peer-to-peer communication application, packet size, transmission time

2. Update
   

(1) Mobile node updates binding to local GNRS server: constant latency.
(2) Local GNRS server hash K times and then sends binding to K grids: routing latencies from local GNRS server to K grids (for simplicity, latency is proportional to the distance between grids)
(3) K grids reply acknowledgements: routing latencies from K grids to original local GNRS server (for simplicity, this latency is proportional to the distance between grids)

update latency T0 = (1) + biggest in (2) + biggest in (3)
or update latency T0 = (1) + biggest in (2) (since after (2), GNRS server is able to answer query)

3. Query
   

(1) Node sends query message to its local GNRS server: constant latency
(2) Local GNRS server hashes K times and pick the nearest grid to forward query message: assume routing latency is proportional to the distance between the two grids.
(3) The nearest grid's router returns binding message to the node: routing latency is same as latency in (2).

query latency T1 = (1) + (2) + (3)

4. Multimedia application (mobile client to static server): event list is pre-generated before simulation
   

Assumption: mobile node A, service provider's static server B, A's original grid router C, A's original grid GNRS server D, A's new grid router E, A's new grid GNRS server F.

(1) Mobile node A sends query message for B to its local GNRS server D, query delay is T1.
(2) A sends service request with binding information to B, the latency is T2.

T2 is proportion to the distance between A and B (approximately distance between C and B + constant distance from A to C)

(3) B sends chunk/packets to A at the original grid T3.

T3 is same as T2 (routing delay from B to A)

(4) chunk/packets delivered successfully, time is T4.

a) Transmission delay T5: T5 = chunk size / transmission rates
b) A sends ACK to B: T6, same as T2 (assume stop & wait transmission)

T4 = T5 + T6 (T4 may vary since T2 may change for different chunk as A is moving)

(5) chunk/packets delivery fails: reroute, delay is T7.

a) delay of discovering the failure: T4
b) latency of A's update: T0 (during T4, A might start updating its binding, so T0 and T4 may overlap)
c) latency of query for A's new binding: T1
d) delay of routing from B to A: T3

T7 <= T4 + T0 + T1 + T3

Total service time T = T1 + T2 + T3 + sum of chunk # of T4 + sum of reroute # of T7

5. Peer-to-Peer application (between two mobile nodes): event list is pre-generated before simulation, bidirectional communication
   

Assumption: mobile node A and B, A's original grid router C, A's original grid GNRS server D, A's new grid router E, A's new grid GNRS server F, B's original grid router G, B's original grid GNRS server H, B's new grid router I, B's new grid GNRS server J.

(1) Mobile node A initiate the communication. A sends query message to its local GNRS server D for B, query delay is T1.
(2) A sends a packet (the first packet carries A's binding information) to B. The latency is T2.

T2 is proportion to the distance between A and B (approximately distance between the two grids + distance from mobile nodes to local routers)

(3) Packet from A to B delivered successfully, time is T3.

a) Transmission delay T4: T4 = packet size / transmission rates
b) A sends ACK to B: T5, same as T2 (assume stop & wait transmission)

T3 = T4 + T5 (T3 may vary since T5 may change for different chunk as A is moving)

(4) Packet delivery fails: reroute, delay is T6.

a) delay of discovering the failure: T3
b) latency of A's update: T0 (during T3, A might start updating its binding, so T0 and T3 may overlap)
c) latency of query for A's new binding: T1
d) delay of routing from B to A: T2

T6 <= T3 + T0 + T1 + T2

(1) -(4) are traffic from A to B. Traffic from B to A (similar to (2)-(4)) might exist at the same time but seldom.

Future optimization / analysis:
(1) In multimedia on demand application, mobile node D sends service request message to service provider server D encapsulated binding information <GUID, NA> so that D can directly send media file to C's NA without sending query to GNRS server. We can analyze the delay of the two strategies in the scenario : a) D use C's NA carried by the service request directly, therefore decrease the query delay; but the risk is that C moves to another grid and therefore increase the reroute delay; b) after receive service request, D still query GNRS server for C's NA.