Java networking

The problem is to figure out the best way to route the packets through

Page 1 of 1

1 Replies - 843 Views - Last Post: 07 May 2009 - 04:01 PM Rate Topic: -----

#1 bhadebe@grinpal.co.za  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 07-May 09

Java networking

Posted 07 May 2009 - 02:15 AM

Attached File  sample_output.txt (3.56K)
Number of downloads: 95Attached File  sample_output.txt (3.56K)
Number of downloads: 95Problem Statement

We can think of a computer network as an undirected graph where nodes represent routers and edges represent connections between the routers. In this network, there are a number of packets, each of which has a source and a target. Over a number of discrete time steps, each packet must travel from its source to its target. During one time step, a packet at router u may move to router v, if there is a link between u and v. However, only one packet may use a link between u and v during a particular time step (if one packet uses a link to go from u to v, no other packet can use that link to go from v to u during the same time step). The problem is to figure out the best way to route the packets through the network so that they get to their destinations as soon as possible.

You will be given an int, 2<=N<=100, representing the number of nodes in the graph. A String[], g, will specify the edges (up to 4950 of them), where each element is of the form "u v", where u and v are distinct integers between 0 and N-1, inclusive, indicating an edge between node u and node v. There will be at most one edge between a pair of nodes. A String[], packets, will specify the packets to be sent in the network, where 10<=|packets|<=2,000. Each element will be formatted as "s t", indicating a packet with source s and target t, where s does not equal t. The graphs will be connected.

Your task is to come up with a routing plan for the packets through the network. You should return a String[], each element of which represents the locations of the packets after each time step. Each element of the String[] should be a space delimited list of the packets' locations at a time step corresponding to the index of the element (the first element of the return corresponds to the locations of the packets after the first time step). The list should give the locations in the same order that the packets are given to you.

For example, consider the simple network with 2 nodes and 2 packets:

N=2

g={"0 1"}

packets={"0 1","1 0"}

In this case, there are two packets trying to go in opposite directions along the one link. One possible return would be:

{"0 0","1 0"}

This indicates that in the first time step, the second packet moves along the link from node 1 to node 0. Since that link is in use, the first packet cannot also use it, so during the second time step, the first packet moves from node 0 to node 1, and at this point all packets have reached their destinations. Another valid return would be {"0 1","1 1","1 0"}. In this return, none of the packets moved during the first time step. While valid, this is clearly suboptimal.

Definition

Class: RoutePackets
Method: route
Parameters: int, String[], String[]
Returns: String[]
Method signature: String[] route(int N, String[] graph, String[] packets)
(Be sure your method is public)

There may be multiple packets corresponding to a single pair of nodes.

Criteria

The original problem statement was part of an online coding competition and was judged based on speed of execution and efficiency of algorithm, and then ranked based on comparison with other entries.

For the purposes of this exercise, the resulting code will be evaluated on:

• Correctness of solution
• Code style and structure
• Efficiency of solution (choice of data structures, algorithms and how they’re utilized, etc)

The solution must be implemented in Java using the standard JRE 1.4 or JRE 1.5 API’s. No 3rd party or custom APIs may be used. Feel free to utilize all facilities of the JRE to improve the efficiency of your solution – multi-threading, for example, may help. Comments in code are important, but not critical – do not waste time making comments look pretty, and only comment when the reasons for your implementation may not be immediately obvious.

Available resources

- Windows XP
- Sun JDK 1.4 or Sun JDK 1.5
- JDK documentation
- Eclipse development IDE
- Notepad.exe

Use these files as input to your final solution:
- graph.txt – a randomly generated, connected, undirected graph.
- packets.txt – a randomly generated set of packet source and targets

This file shows some sample output for the above graph/packet configuration.
- sample-output.txt

2-3 hours.

Hints

The problem is a difficult one. Here are some tips to get you going:

- The code for reading the input data has already been written for you.
- The majority of your time should be spent solving two key problems: the shortest paths for the packets to travel, and the mechanism for moving the packets between source and destination.
- The shortest path problem can be solved using a number of algorithms. A typical approach is recursively using a depth or breadth first search. Use the internet to search for solutions to the shortest path problem if you need to. (Most resources may provide pseudo code for directed graphs. Remember – this is an undirected graph: you can travel in both directions!)
- Make it easier for yourself to iterate through collections of nodes, edges and packets by putting the input data into a more useful data structure.
- Focus on solving the problem before dealing with efficiency. Once you have a working solution, consider areas that may offer large benefits for small amounts of effort.

Is This A Good Question/Topic? 0
  • +

Replies To: Java networking

#2 BigAnt  Icon User is offline

  • May Your Swords Stay Sharp
  • member icon

Reputation: 101
  • View blog
  • Posts: 2,392
  • Joined: 16-August 08

Re: Java networking

Posted 07 May 2009 - 04:01 PM

What is this your final project? Can't just post here and have no efforts on your half. We have rules here which you have blatantly disregarded:

[rules][/rules]

Here may be some useful links:
Shortest Path:http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Min. Spanning tree: http://en.wikipedia....m%27s_algorithm
Link-state Routing protocol: http://en.wikipedia....outing_protocol
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1