Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.Collections;
- import java.util.List;
- import java.util.PriorityQueue;
- public class DijkstraAlgor {
- public static void computePaths(DijkstraRouter source)
- {
- source.minDistance = 0.;
- PriorityQueue<DijkstraRouter> vertexQueue = new PriorityQueue<DijkstraRouter>();
- vertexQueue.add(source);
- while (!vertexQueue.isEmpty()) {
- DijkstraRouter router = vertexQueue.poll();
- // Visit each edge exiting u
- for (Link L : router.adjacencies)
- {
- DijkstraRouter v = L.NextRouter;
- double cost = L.cost;
- double distanceThroughU = router.minDistance + cost;
- if (distanceThroughU < v.minDistance) {
- vertexQueue.remove(v);
- v.minDistance = distanceThroughU ;
- v.previous = router;
- vertexQueue.add(v);
- }
- }
- }
- }
- public static List<DijkstraRouter> getShortestPathTo(DijkstraRouter NextRouter){
- List<DijkstraRouter> path = new ArrayList<DijkstraRouter>();
- for (DijkstraRouter DijkstraRouter = NextRouter; DijkstraRouter != null; DijkstraRouter = DijkstraRouter.previous){
- path.add(DijkstraRouter);
- //For loop to check links of our current router. Check to see if the NextRouter of that link is the same as the computed NextRouter. Increase delta is if does.
- for( int i = 0; i < DijkstraRouter.adjacencies.length; i++) {
- if ( DijkstraRouter.adjacencies[i].NextRouter.equals(NextRouter)){
- DijkstraRouter.adjacencies[i].setLinkUsage();
- }
- } //end of this delta setter
- }
- Collections.reverse(path);//Reverses the order so that you see the path from the perspective of the source router
- return path;
- }
- public static void main(String[] args){
- double Dpq = 0.1;
- double PacketLength = 12000;
- double Ti = 0.001;
- //Setting up naming scheme for topology
- DijkstraRouter Router1 = new DijkstraRouter("Router1");
- DijkstraRouter Router2 = new DijkstraRouter("Router2");
- DijkstraRouter Router3 = new DijkstraRouter("Router3");
- DijkstraRouter Router4 = new DijkstraRouter("Router4");
- DijkstraRouter Router5 = new DijkstraRouter("Router5");
- DijkstraRouter Router6 = new DijkstraRouter("Router6");
- DijkstraRouter Router7 = new DijkstraRouter("Router7");
- DijkstraRouter Router8 = new DijkstraRouter("Router8");
- DijkstraRouter Router9 = new DijkstraRouter("Router9");
- DijkstraRouter Router10 = new DijkstraRouter("Router10");
- DijkstraRouter Router11 = new DijkstraRouter("Router11");
- DijkstraRouter Router12 = new DijkstraRouter("Router12");
- DijkstraRouter Router13 = new DijkstraRouter("Router13");
- DijkstraRouter Router14 = new DijkstraRouter("Router14");
- DijkstraRouter Router15 = new DijkstraRouter("Router15");
- DijkstraRouter Router16 = new DijkstraRouter("Router16");
- DijkstraRouter Router17 = new DijkstraRouter("Router17");
- DijkstraRouter Router18 = new DijkstraRouter("Router18");
- DijkstraRouter Router19 = new DijkstraRouter("Router19");
- DijkstraRouter Router20 = new DijkstraRouter("Router20");
- DijkstraRouter Router21 = new DijkstraRouter("Router21");
- DijkstraRouter Router22 = new DijkstraRouter("Router22");
- DijkstraRouter Router23 = new DijkstraRouter("Router23");
- DijkstraRouter Router24 = new DijkstraRouter("Router24");
- DijkstraRouter Router25 = new DijkstraRouter("Router25");
- DijkstraRouter Router26 = new DijkstraRouter("Router26");
- //FORMAT FOR ADJCENCY INFO
- // | I | J | | Cij | | Lij |
- /*
- 1 2 1500000.0 184.0
- 1 3 1500000.0 840.0
- 2 4 1500000.0 707.0
- 2 6 2000000.0 882.0
- 3 7 1500000.0 120.0
- 3 8 2000000.0 497.0
- 4 5 1500000.0 572.0
- 5 7 2000000.0 941.0
- 6 9 2000000.0 128.0
- 7 23 2500000.0 492.0
- 8 10 1500000.0 344.0
- 9 11 2000000.0 782.0
- 10 13 1500000.0 548.0
- 11 14 2000000.0 318.0
- 12 14 2000000.0 273.0
- 12 18 2000000.0 50.0
- 12 21 1500000.0 390.0
- 13 16 2000000.0 327.0
- 15 17 2000000.0 735.0
- 15 23 1500000.0 337.0
- 15 26 2000000.0 576.0
- 16 24 2000000.0 455.0
- 17 19 1500000.0 758.0
- 18 22 1500000.0 332.0
- 19 21 1500000.0 160.0
- 20 25 2000000.0 942.0
- 20 26 1500000.0 549.0
- 22 24 1500000.0 310.0
- 24 25 1500000.0 403.0
- */
- //LINK DATA CONFIGURATION//-----------------------------------------------------------//
- //ROUTER 1 ADJCENCIES
- Router1.adjacencies = new Link[]{
- new Link(Router2, 66.67, 1500000, 184, 0),
- new Link(Router3, 66.67, 1500000, 840, 0)};
- //ROUTER 2 ADJCENCIES
- Router2.adjacencies = new Link[]{
- new Link(Router1, 66.67, 1500000, 184, 0),
- new Link(Router4, 66.67, 1500000, 707, 0),
- new Link(Router6, 50.0, 2000000, 882, 0)};
- //ROUTER 3 ADJCENCIES
- Router3.adjacencies = new Link[]{
- new Link(Router1, 66.67, 1500000, 840, 0),
- new Link(Router7, 66.67, 1500000, 120, 0),
- new Link(Router8, 50.0, 2000000, 497, 0)};
- //ROUTER 4 ADJCENCIES
- Router4.adjacencies = new Link[]{
- new Link(Router2, 66.67, 1500000, 707, 0),
- new Link(Router5, 66.67, 1500000, 572, 0)};
- //ROUTER 5 ADJCENCIES
- Router5.adjacencies = new Link[]{
- new Link(Router4, 66.67, 1500000, 572, 0),
- new Link(Router7, 50.0, 2000000, 941, 0)};
- //ROUTER 6 ADJCENCIES
- Router6.adjacencies = new Link[]{
- new Link(Router2, 50.0, 2000000, 882, 0),
- new Link(Router9, 50.0, 2000000, 128, 0)};
- //ROUTER 7 ADJCENCIES
- Router7.adjacencies = new Link[]{
- new Link(Router3, 66.67, 1500000, 120, 0),
- new Link(Router5, 50.0, 2000000, 941, 0),
- new Link(Router23, 40.0, 2500000, 492, 0)};
- //ROUTER 8 ADJCENCIES
- Router8.adjacencies = new Link[]{
- new Link(Router3, 50.0, 2000000, 497, 0),
- new Link(Router10, 66.67, 1500000, 344, 0)};
- //ROUTER 9 ADJCENCIES
- Router9.adjacencies = new Link[]{
- new Link(Router6, 50.0, 2000000, 128, 0),
- new Link(Router11, 50.0, 2000000, 782, 0)};
- //ROUTER 10 ADJCENCIES
- Router10.adjacencies = new Link[]{
- new Link(Router8, 66.67, 1500000, 344, 0 ),
- new Link(Router13, 66.67, 1500000, 548, 0)};
- //ROUTER 11 ADJCENCIES
- Router11.adjacencies = new Link[]{
- new Link(Router9, 50.0, 2000000, 782, 0),
- new Link(Router14, 50.0, 2000000, 318, 0)};
- //ROUTER 12 ADJCENCIES
- Router12.adjacencies = new Link[]{
- new Link(Router14, 50.0, 2000000, 273, 0),
- new Link(Router18, 50.0, 2000000, 50, 0 ),
- new Link(Router21, 66.67, 1500000, 390, 0)};
- //ROUTER 13 ADJCENCIES
- Router13.adjacencies = new Link[]{
- new Link(Router10, 66.67, 1500000, 548, 0),
- new Link(Router16, 50.0, 2000000, 327, 0)};
- //ROUTER 14 ADJCENCIES
- Router14.adjacencies = new Link[]{
- new Link(Router11, 50.0, 2000000, 318, 0),
- new Link(Router12, 50.0, 2000000, 273, 0)};
- //ROUTER 15 ADJCENCIES
- Router15.adjacencies = new Link[]{
- new Link(Router17, 50.0, 2000000, 735, 0),
- new Link(Router23, 66.67, 1500000, 337, 0),
- new Link(Router26, 50.0, 2000000, 576, 0)};
- //ROUTER 16 ADJCENCIES
- Router16.adjacencies = new Link[]{
- new Link(Router13, 50.0, 2000000, 327, 0),
- new Link(Router24, 50.0, 2000000, 455, 0)};
- //ROUTER 17 ADJCENCIES
- Router17.adjacencies = new Link[]{
- new Link(Router15, 50.0, 2000000, 735, 0),
- new Link(Router19, 66.67, 1500000, 758, 0)};
- //ROUTER 18 ADJCENCIES
- Router18.adjacencies = new Link[]{
- new Link(Router12, 50.0, 2000000, 50, 0 ),
- new Link(Router22, 66.67, 1500000, 332, 0)};
- //ROUTER 19 ADJCENCIES
- Router19.adjacencies = new Link[]{
- new Link(Router17, 66.67, 1500000, 758, 0),
- new Link(Router21, 66.67, 1500000, 160, 0)};
- //ROUTER 20 AJACENCIES
- Router20.adjacencies = new Link[]{
- new Link(Router25, 50.0, 2000000, 942, 0),
- new Link(Router26, 66.67, 1500000, 549, 0)};
- //ROUTER 21 AJACENCIES
- Router21.adjacencies = new Link []{
- new Link(Router12, 66.67, 1500000, 390, 0),
- new Link(Router19, 66.67, 1500000, 160, 0)};
- //ROUTER 22 AJACENCIES
- Router22.adjacencies = new Link[]{
- new Link(Router18, 66.67, 1500000, 332, 0),
- new Link(Router24, 66.67, 1500000, 310, 0)};
- //ROUTER 23 AJACENCIES
- Router23.adjacencies = new Link[]{
- new Link(Router7, 40.0, 2500000, 492, 0),
- new Link(Router15, 66.67, 1500000, 337, 0)};
- //ROUTER 24 AJACENCIES
- Router24.adjacencies = new Link[]{
- new Link(Router16, 50.0, 2000000, 455, 0),
- new Link(Router22, 66.67, 1500000, 310, 0),
- new Link(Router25, 66.67, 1500000, 403, 0)};
- //ROUTER 25 ADJACENCIES
- Router25.adjacencies = new Link []{
- new Link(Router20, 50.0, 2000000, 942, 0),
- new Link(Router24, 66.67, 1500000, 403, 0)};
- //ROUTER 26 AJACENCIES
- Router26.adjacencies = new Link[]{
- new Link(Router20, 66.67, 1500000, 549, 0),
- new Link(Router15, 50.0, 2000000, 576, 0)};
- DijkstraRouter[] Routers = { Router1, Router2, Router3, Router4, Router5, Router6, Router7, Router8, Router9, Router10,
- Router11, Router12, Router13, Router14, Router15, Router16, Router17, Router18, Router19, Router20, Router21,
- Router22, Router23, Router24, Router25, Router26 };
- computePaths(Router1);
- //OUTPUT FUNCTION======================================================================================================
- //OUTPUT AND EXECUTION OF PATHS
- for (DijkstraRouter router : Routers)
- {
- //System.out.println("\n"+router);
- List<DijkstraRouter> path = getShortestPathTo(router);
- //System.out.println("Path: " + path+"\n");
- }
- //OUTPUT OF THE LINK DELTA VALUES
- for (DijkstraRouter router : Routers){
- System.out.println("\n"+router);
- for ( int i = 0; i < router.adjacencies.length; i++){
- if(router.adjacencies[i].getLinkUsage()>0){
- double Fij = router.adjacencies[i].getLinkUsage() * Dpq * PacketLength ;
- double Cij = router.adjacencies[i].getTransCap();
- double delta = Fij/PacketLength;
- double Pij = Cij*0.000005;
- double LinkAverageDelay = (1/delta)*((Fij/(Cij-Fij))+(Pij+Ti)*(Fij/PacketLength));
- System.out.println("\nDelta from " +router+" to "+ router.adjacencies[i].NextRouter + " is: " + router.adjacencies[i].getLinkUsage());
- System.out.println("The average delay for this link is " + LinkAverageDelay);
- }
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement