API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Dec 1st, 2015
76
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 10.38 KB | None | 0 0
raw download clone embed print report
  1. import java.util.ArrayList;
  2. import java.util.Collections;
  3. import java.util.List;
  4. import java.util.PriorityQueue;
  5.  
  6. public class DijkstraAlgor {
  7.  
  8.  
  9.  
  10. public static void computePaths(DijkstraRouter source)
  11. {
  12. source.minDistance = 0.;
  13. PriorityQueue<DijkstraRouter> vertexQueue = new PriorityQueue<DijkstraRouter>();
  14. vertexQueue.add(source);
  15.  
  16. while (!vertexQueue.isEmpty()) {
  17. DijkstraRouter router = vertexQueue.poll();
  18.  
  19. // Visit each edge exiting u
  20. for (Link L : router.adjacencies)
  21. {
  22. DijkstraRouter v = L.NextRouter;
  23. double cost = L.cost;
  24. double distanceThroughU = router.minDistance + cost;
  25. if (distanceThroughU < v.minDistance) {
  26. vertexQueue.remove(v);
  27.  
  28. v.minDistance = distanceThroughU ;
  29. v.previous = router;
  30. vertexQueue.add(v);
  31. }
  32. }
  33. }
  34. }
  35.  
  36.  
  37.  
  38. public static List<DijkstraRouter> getShortestPathTo(DijkstraRouter NextRouter){
  39. List<DijkstraRouter> path = new ArrayList<DijkstraRouter>();
  40. for (DijkstraRouter DijkstraRouter = NextRouter; DijkstraRouter != null; DijkstraRouter = DijkstraRouter.previous){
  41. path.add(DijkstraRouter);
  42.  
  43.  
  44. //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.
  45. for( int i = 0; i < DijkstraRouter.adjacencies.length; i++) {
  46. if ( DijkstraRouter.adjacencies[i].NextRouter.equals(NextRouter)){
  47. DijkstraRouter.adjacencies[i].setLinkUsage();
  48. }
  49. } //end of this delta setter
  50. }
  51.  
  52. Collections.reverse(path);//Reverses the order so that you see the path from the perspective of the source router
  53. return path;
  54. }
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
  61.  
  62.  
  63.  
  64. public static void main(String[] args){
  65.  
  66. double Dpq = 0.1;
  67. double PacketLength = 12000;
  68. double Ti = 0.001;
  69.  
  70. //Setting up naming scheme for topology
  71. DijkstraRouter Router1 = new DijkstraRouter("Router1");
  72. DijkstraRouter Router2 = new DijkstraRouter("Router2");
  73. DijkstraRouter Router3 = new DijkstraRouter("Router3");
  74. DijkstraRouter Router4 = new DijkstraRouter("Router4");
  75. DijkstraRouter Router5 = new DijkstraRouter("Router5");
  76. DijkstraRouter Router6 = new DijkstraRouter("Router6");
  77. DijkstraRouter Router7 = new DijkstraRouter("Router7");
  78. DijkstraRouter Router8 = new DijkstraRouter("Router8");
  79. DijkstraRouter Router9 = new DijkstraRouter("Router9");
  80. DijkstraRouter Router10 = new DijkstraRouter("Router10");
  81. DijkstraRouter Router11 = new DijkstraRouter("Router11");
  82. DijkstraRouter Router12 = new DijkstraRouter("Router12");
  83. DijkstraRouter Router13 = new DijkstraRouter("Router13");
  84. DijkstraRouter Router14 = new DijkstraRouter("Router14");
  85. DijkstraRouter Router15 = new DijkstraRouter("Router15");
  86. DijkstraRouter Router16 = new DijkstraRouter("Router16");
  87. DijkstraRouter Router17 = new DijkstraRouter("Router17");
  88. DijkstraRouter Router18 = new DijkstraRouter("Router18");
  89. DijkstraRouter Router19 = new DijkstraRouter("Router19");
  90. DijkstraRouter Router20 = new DijkstraRouter("Router20");
  91. DijkstraRouter Router21 = new DijkstraRouter("Router21");
  92. DijkstraRouter Router22 = new DijkstraRouter("Router22");
  93. DijkstraRouter Router23 = new DijkstraRouter("Router23");
  94. DijkstraRouter Router24 = new DijkstraRouter("Router24");
  95. DijkstraRouter Router25 = new DijkstraRouter("Router25");
  96. DijkstraRouter Router26 = new DijkstraRouter("Router26");
  97.  
  98.  
  99.  
  100. //FORMAT FOR ADJCENCY INFO
  101.  
  102. // | I | J | | Cij | | Lij |
  103. /*
  104. 1 2 1500000.0 184.0
  105. 1 3 1500000.0 840.0
  106. 2 4 1500000.0 707.0
  107. 2 6 2000000.0 882.0
  108. 3 7 1500000.0 120.0
  109. 3 8 2000000.0 497.0
  110. 4 5 1500000.0 572.0
  111. 5 7 2000000.0 941.0
  112. 6 9 2000000.0 128.0
  113. 7 23 2500000.0 492.0
  114. 8 10 1500000.0 344.0
  115. 9 11 2000000.0 782.0
  116. 10 13 1500000.0 548.0
  117. 11 14 2000000.0 318.0
  118. 12 14 2000000.0 273.0
  119. 12 18 2000000.0 50.0
  120. 12 21 1500000.0 390.0
  121. 13 16 2000000.0 327.0
  122. 15 17 2000000.0 735.0
  123. 15 23 1500000.0 337.0
  124. 15 26 2000000.0 576.0
  125. 16 24 2000000.0 455.0
  126. 17 19 1500000.0 758.0
  127. 18 22 1500000.0 332.0
  128. 19 21 1500000.0 160.0
  129. 20 25 2000000.0 942.0
  130. 20 26 1500000.0 549.0
  131. 22 24 1500000.0 310.0
  132. 24 25 1500000.0 403.0
  133. */
  134.  
  135. //LINK DATA CONFIGURATION//-----------------------------------------------------------//
  136. //ROUTER 1 ADJCENCIES
  137. Router1.adjacencies = new Link[]{
  138. new Link(Router2, 66.67, 1500000, 184, 0),
  139. new Link(Router3, 66.67, 1500000, 840, 0)};
  140.  
  141.  
  142. //ROUTER 2 ADJCENCIES
  143. Router2.adjacencies = new Link[]{
  144. new Link(Router1, 66.67, 1500000, 184, 0),
  145. new Link(Router4, 66.67, 1500000, 707, 0),
  146. new Link(Router6, 50.0, 2000000, 882, 0)};
  147.  
  148.  
  149. //ROUTER 3 ADJCENCIES
  150. Router3.adjacencies = new Link[]{
  151. new Link(Router1, 66.67, 1500000, 840, 0),
  152. new Link(Router7, 66.67, 1500000, 120, 0),
  153. new Link(Router8, 50.0, 2000000, 497, 0)};
  154.  
  155.  
  156. //ROUTER 4 ADJCENCIES
  157. Router4.adjacencies = new Link[]{
  158. new Link(Router2, 66.67, 1500000, 707, 0),
  159. new Link(Router5, 66.67, 1500000, 572, 0)};
  160.  
  161.  
  162. //ROUTER 5 ADJCENCIES
  163. Router5.adjacencies = new Link[]{
  164. new Link(Router4, 66.67, 1500000, 572, 0),
  165. new Link(Router7, 50.0, 2000000, 941, 0)};
  166.  
  167.  
  168. //ROUTER 6 ADJCENCIES
  169. Router6.adjacencies = new Link[]{
  170. new Link(Router2, 50.0, 2000000, 882, 0),
  171. new Link(Router9, 50.0, 2000000, 128, 0)};
  172.  
  173.  
  174. //ROUTER 7 ADJCENCIES
  175. Router7.adjacencies = new Link[]{
  176. new Link(Router3, 66.67, 1500000, 120, 0),
  177. new Link(Router5, 50.0, 2000000, 941, 0),
  178. new Link(Router23, 40.0, 2500000, 492, 0)};
  179.  
  180.  
  181. //ROUTER 8 ADJCENCIES
  182. Router8.adjacencies = new Link[]{
  183. new Link(Router3, 50.0, 2000000, 497, 0),
  184. new Link(Router10, 66.67, 1500000, 344, 0)};
  185.  
  186.  
  187. //ROUTER 9 ADJCENCIES
  188. Router9.adjacencies = new Link[]{
  189. new Link(Router6, 50.0, 2000000, 128, 0),
  190. new Link(Router11, 50.0, 2000000, 782, 0)};
  191.  
  192.  
  193. //ROUTER 10 ADJCENCIES
  194. Router10.adjacencies = new Link[]{
  195. new Link(Router8, 66.67, 1500000, 344, 0 ),
  196. new Link(Router13, 66.67, 1500000, 548, 0)};
  197.  
  198.  
  199. //ROUTER 11 ADJCENCIES
  200. Router11.adjacencies = new Link[]{
  201. new Link(Router9, 50.0, 2000000, 782, 0),
  202. new Link(Router14, 50.0, 2000000, 318, 0)};
  203.  
  204.  
  205. //ROUTER 12 ADJCENCIES
  206. Router12.adjacencies = new Link[]{
  207. new Link(Router14, 50.0, 2000000, 273, 0),
  208. new Link(Router18, 50.0, 2000000, 50, 0 ),
  209. new Link(Router21, 66.67, 1500000, 390, 0)};
  210.  
  211.  
  212. //ROUTER 13 ADJCENCIES
  213. Router13.adjacencies = new Link[]{
  214. new Link(Router10, 66.67, 1500000, 548, 0),
  215. new Link(Router16, 50.0, 2000000, 327, 0)};
  216.  
  217. //ROUTER 14 ADJCENCIES
  218. Router14.adjacencies = new Link[]{
  219. new Link(Router11, 50.0, 2000000, 318, 0),
  220. new Link(Router12, 50.0, 2000000, 273, 0)};
  221.  
  222.  
  223. //ROUTER 15 ADJCENCIES
  224. Router15.adjacencies = new Link[]{
  225. new Link(Router17, 50.0, 2000000, 735, 0),
  226. new Link(Router23, 66.67, 1500000, 337, 0),
  227. new Link(Router26, 50.0, 2000000, 576, 0)};
  228.  
  229.  
  230. //ROUTER 16 ADJCENCIES
  231. Router16.adjacencies = new Link[]{
  232. new Link(Router13, 50.0, 2000000, 327, 0),
  233. new Link(Router24, 50.0, 2000000, 455, 0)};
  234.  
  235.  
  236. //ROUTER 17 ADJCENCIES
  237. Router17.adjacencies = new Link[]{
  238. new Link(Router15, 50.0, 2000000, 735, 0),
  239. new Link(Router19, 66.67, 1500000, 758, 0)};
  240.  
  241.  
  242. //ROUTER 18 ADJCENCIES
  243. Router18.adjacencies = new Link[]{
  244. new Link(Router12, 50.0, 2000000, 50, 0 ),
  245. new Link(Router22, 66.67, 1500000, 332, 0)};
  246.  
  247.  
  248. //ROUTER 19 ADJCENCIES
  249. Router19.adjacencies = new Link[]{
  250. new Link(Router17, 66.67, 1500000, 758, 0),
  251. new Link(Router21, 66.67, 1500000, 160, 0)};
  252.  
  253.  
  254. //ROUTER 20 AJACENCIES
  255. Router20.adjacencies = new Link[]{
  256. new Link(Router25, 50.0, 2000000, 942, 0),
  257. new Link(Router26, 66.67, 1500000, 549, 0)};
  258.  
  259. //ROUTER 21 AJACENCIES
  260. Router21.adjacencies = new Link []{
  261. new Link(Router12, 66.67, 1500000, 390, 0),
  262. new Link(Router19, 66.67, 1500000, 160, 0)};
  263.  
  264.  
  265. //ROUTER 22 AJACENCIES
  266. Router22.adjacencies = new Link[]{
  267. new Link(Router18, 66.67, 1500000, 332, 0),
  268. new Link(Router24, 66.67, 1500000, 310, 0)};
  269.  
  270.  
  271. //ROUTER 23 AJACENCIES
  272. Router23.adjacencies = new Link[]{
  273. new Link(Router7, 40.0, 2500000, 492, 0),
  274. new Link(Router15, 66.67, 1500000, 337, 0)};
  275.  
  276.  
  277. //ROUTER 24 AJACENCIES
  278. Router24.adjacencies = new Link[]{
  279. new Link(Router16, 50.0, 2000000, 455, 0),
  280. new Link(Router22, 66.67, 1500000, 310, 0),
  281. new Link(Router25, 66.67, 1500000, 403, 0)};
  282.  
  283.  
  284. //ROUTER 25 ADJACENCIES
  285. Router25.adjacencies = new Link []{
  286. new Link(Router20, 50.0, 2000000, 942, 0),
  287. new Link(Router24, 66.67, 1500000, 403, 0)};
  288.  
  289.  
  290. //ROUTER 26 AJACENCIES
  291. Router26.adjacencies = new Link[]{
  292. new Link(Router20, 66.67, 1500000, 549, 0),
  293. new Link(Router15, 50.0, 2000000, 576, 0)};
  294.  
  295.  
  296.  
  297.  
  298.  
  299. DijkstraRouter[] Routers = { Router1, Router2, Router3, Router4, Router5, Router6, Router7, Router8, Router9, Router10,
  300. Router11, Router12, Router13, Router14, Router15, Router16, Router17, Router18, Router19, Router20, Router21,
  301. Router22, Router23, Router24, Router25, Router26 };
  302.  
  303. computePaths(Router1);
  304.  
  305.  
  306. //OUTPUT FUNCTION======================================================================================================
  307.  
  308.  
  309.  
  310. //OUTPUT AND EXECUTION OF PATHS
  311. for (DijkstraRouter router : Routers)
  312. {
  313. //System.out.println("\n"+router);
  314. List<DijkstraRouter> path = getShortestPathTo(router);
  315. //System.out.println("Path: " + path+"\n");
  316. }
  317.  
  318. //OUTPUT OF THE LINK DELTA VALUES
  319. for (DijkstraRouter router : Routers){
  320.  
  321.  
  322.  
  323.  
  324. System.out.println("\n"+router);
  325. for ( int i = 0; i < router.adjacencies.length; i++){
  326. if(router.adjacencies[i].getLinkUsage()>0){
  327. double Fij = router.adjacencies[i].getLinkUsage() * Dpq * PacketLength ;
  328. double Cij = router.adjacencies[i].getTransCap();
  329. double delta = Fij/PacketLength;
  330. double Pij = Cij*0.000005;
  331. double LinkAverageDelay = (1/delta)*((Fij/(Cij-Fij))+(Pij+Ti)*(Fij/PacketLength));
  332. System.out.println("\nDelta from " +router+" to "+ router.adjacencies[i].NextRouter + " is: " + router.adjacencies[i].getLinkUsage());
  333. System.out.println("The average delay for this link is " + LinkAverageDelay);
  334. }
  335. }
  336. }
  337.  
  338.  
  339.  
  340.  
  341.  
  342.  
  343.  
  344.  
  345. }
  346. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!