001/******************************************************************************* 002 * Copyright (c) 2017 Pablo Pavon Marino and others. 003 * All rights reserved. This program and the accompanying materials 004 * are made available under the terms of the 2-clause BSD License 005 * which accompanies this distribution, and is available at 006 * https://opensource.org/licenses/BSD-2-Clause 007 * 008 * Contributors: 009 * Pablo Pavon Marino and others - initial API and implementation 010 *******************************************************************************/ 011 012package com.net2plan.examples.ocnbook.reports; 013 014import com.net2plan.interfaces.networkDesign.*; 015import com.net2plan.utils.Constants.RoutingType; 016import com.net2plan.utils.InputParameter; 017import com.net2plan.utils.Triple; 018 019import java.text.DecimalFormat; 020import java.util.List; 021import java.util.Map; 022 023/** 024 * This report receives as an input a network design, where the network is assumed to be based on packet switching, and estimates the packet delay 025 * of the different flows. 026 * 027 * @net2plan.keywords 028 * @net2plan.ocnbooksections Section 3.2 029 * @net2plan.inputParameters 030 * @author Pablo Pavon-Marino 031 */ 032public class Report_delay implements IReport 033{ 034 private InputParameter hurstParameter = new InputParameter ("hurstParameter" , (double) 0.5 , "Hurst parameter (H) of self-similar sources [0.5, 1) (M/M/1 model when H = 0.5)" , 0.5 , true, 1, false); 035 private InputParameter averagePacketLength_bits = new InputParameter ("averagePacketLength_bits" , (double) 500*8 , "Average packet length in bits" , 0 , false , Double.MAX_VALUE, true); 036 private InputParameter linkCapacityUnits_bps = new InputParameter ("linkCapacityUnits_bps" , (double) 1e6 , "Units in bps in which the capacity of the links is measured" , 0 , false , Double.MAX_VALUE, true); 037 038 @Override 039 public String executeReport(NetPlan netPlan, Map<String, String> reportParameters, Map<String, String> net2planParameters) 040 { 041 /* Initialize all InputParameter objects defined in this object (this uses Java reflection) */ 042 InputParameter.initializeAllInputParameterFieldsOfObject(this, reportParameters); 043 044 if (!netPlan.hasRoutes()) 045 { 046 return "<html><body><p>No delay information available. Routing is not defined.</p></body></html>"; 047 } 048 049 final int E = netPlan.getNumberOfLinks(); 050 final int D = netPlan.getNumberOfDemands(); 051 final int R = netPlan.getNumberOfRoutes(); 052 053 StringBuilder out = new StringBuilder(); 054 DecimalFormat df_6 = new DecimalFormat("#.######"); 055 out.append("<html><body>"); 056 out.append("<head><title>Packet delay report</title></head>"); 057 out.append("<h1>Introduction</h1>"); 058 out.append("<p>This report receives as an input a network design, where the network is assumed to be based on packet switching, and estimates the packet delay of the different flows.</p>"); 059 out.append("<h1>Motivation</h1>"); 060 out.append("<p>In packet-switched networks, traffic sources split data into smaller pieces called packets, and transmit them attached to a header with control information. Per each packet received, packet-switching nodes read its header and take appropriate forwarding decisions, according to the routing plan configured. In real networks, traffic is highly unpredictable and thus modelled as random processes. When we say that a traffic source <em>d</em> generates <em>h_d</em> traffic units, we refer to a time average. Instantaneous traffic generated oscillates very fast and uncontrollably from peak intervals (generating more traffic than the average) to valley intervals (generating less traffic than the average).</p>"); 061 out.append("<p>The traffic carried by a link is the aggregation (multiplexing) of the traffic from all the sources routed through this link. At a given moment, it is very likely that some of the sources aggregated are in a peak, while others are in a valley. They compensate each other. Thus, you do not need a link capacity equal to the sum of the peak traffics of all the sources, but a capacity between the sum of the averages and the sum of the peaks. We say that multiplexing sources provides an <em>statistical multiplexing gain</em>.</p>"); 062 out.append("<p>Statistical multiplexing gain is the powering fact propeling packet switching. Since it is very common that sources have peaks of traffic several times higher than their average (e.g. 2 or 3 times). However, at unpredictable moments in time, peak traffic intervals coincide and link capacities are not enough to forward traffic. Then, nodes store packets in queues, so they are delayed until they can be transmitted (this delay is known as queuing delay). If this situation remains, queues are filled provoking packet drops. We say that the link is congested or saturated. Note that if the link capacity is below the sum of the average traffic generated by the traversing sources, a large amount of packet drops will always occur, whatever buffer you allocate in the nodes. Network designs must enforce always that link capacities are not below the sum of the averages of the traffics to be carried.</p>"); 063 out.append("<p>Network design tries to model statistically delays and drops in order to minimize their effects. Traffic models capture not only the average of each traffic source, but also a measure of its burstiness. Intuitively, it is clear that the more steep and long that the peak-valley intervals are (or the more bursty the traffic is), the higher the queuing delay. This is because, during low load intervals, the link is underutilized with negligible delays, but during peak traffic intervals packets need to be buffered and can suffer large queuing delays or drops. Naturally, a zero queuing delay occurs when the traffic is perfectly constant (not random).</p>"); 064 out.append("<p>This report estimates the link, path and demand delays using a self-similar model, where the average queueing delay in a link depends on the link capacity, its average traffic, and a so-called <em>Hurst parameter</em> measuring its degree of self-similarity.</p>"); 065 out.append("<p>For more information:</p>"); 066 out.append("<ul><li><a href=\"http://www.wiley.com/WileyCDA/WileyTitle/productCd-1119013356.html\">Pablo Pavón Mariño, \"Optimization of computer networks. Modeling and algorithms. A hands-on approach\", Wiley 2016\"</a></li></ul>"); 067 068 // Link metrics 069 double[] T_e_prop = new double [E]; 070 double[] T_e_tx = new double [E]; 071 double[] T_e_buf = new double [E]; 072 double[] T_e = new double [E]; 073 for (Link e : netPlan.getLinks()) 074 { 075 final double rho_e = e.getUtilization(); 076 T_e_prop [e.getIndex()] = e.getPropagationDelayInMs(); 077 T_e_tx [e.getIndex()] = 1000 * averagePacketLength_bits.getDouble() / (e.getCapacity() * linkCapacityUnits_bps.getDouble()); 078 T_e_buf [e.getIndex()] = 1000 * averagePacketLength_bits.getDouble() / (e.getCapacity() * linkCapacityUnits_bps.getDouble()) * Math.pow(rho_e, 1/(2*(1-hurstParameter.getDouble()))) / Math.pow(1-rho_e , hurstParameter.getDouble()/(1 - hurstParameter.getDouble())); 079 T_e [e.getIndex()] = T_e_prop [e.getIndex()] + T_e_tx [e.getIndex()] + T_e_buf [e.getIndex()]; 080 } 081 082 // Route metrics 083 double[] T_r_prop = new double [R]; 084 double[] T_r_tx = new double [R]; 085 double[] T_r_buf = new double [R]; 086 double[] T_r = new double [R]; 087 for (Route r : netPlan.getRoutes()) 088 for (Link e : r.getSeqLinks()) 089 { 090 T_r_prop [r.getIndex()] += T_e_prop [e.getIndex()]; 091 T_r_tx [r.getIndex()] += T_e_tx [e.getIndex()]; 092 T_r_buf [r.getIndex()] += T_e_buf [e.getIndex()]; 093 T_r [r.getIndex()] += T_e [e.getIndex()]; 094 } 095 096 // Demand metrics 097 double[] T_d_prop = new double [D]; 098 double[] T_d_tx = new double [D]; 099 double[] T_d_buf = new double [D]; 100 double[] T_d = new double [D]; 101 for (Demand d : netPlan.getDemands()) 102 for (Route r : d.getRoutes()) 103 { 104 final double weightFactor = d.getCarriedTraffic() == 0? 0 : r.getCarriedTraffic() / d.getCarriedTraffic(); 105 T_d_prop [d.getIndex()] += weightFactor * T_r_prop [r.getIndex()]; 106 T_d_tx [d.getIndex()] += weightFactor * T_r_tx [r.getIndex()]; 107 T_d_buf [d.getIndex()] += weightFactor * T_r_buf [r.getIndex()]; 108 T_d [d.getIndex()] += weightFactor * T_r [r.getIndex()]; 109 } 110 111 // Network metrics 112 final double sumCarriedTraffic = netPlan.getVectorRouteCarriedTraffic().zSum(); 113 double avNetDelay_T = 0; 114 double avNetDelay_T_prop = 0; 115 for (Route r : netPlan.getRoutes()) 116 { 117 avNetDelay_T += r.getCarriedTraffic() * T_r [r.getIndex()]; 118 avNetDelay_T_prop += r.getCarriedTraffic() * T_r_prop [r.getIndex()]; 119 } 120 avNetDelay_T /= sumCarriedTraffic; 121 avNetDelay_T_prop /= sumCarriedTraffic; 122 123 out.append("<h2>Link delay information</h2>"); 124 out.append("<table border='1'>"); 125 out.append("<tr><th><b>Link index</a></b></th><th><b>Origin node</b></th><th><b>Destination node</b></th><th><b>Propagation delay (ms)</b></th><th><b>Transmission delay (ms)</b></th><th><b>Queuing delay (ms)</b></th><th><b>Total delay (ms)</b></th><th><b>Attributes</a></b></th>"); 126 for (Link e : netPlan.getLinks()) 127 { 128 final int linkId = e.getIndex(); 129 out.append(String.format("<tr><td>%d</td><td>%d (%s)</td><td>%d (%s)</td><td>%.3g</td><td>%.3g</td><td>%.3g</td><td>%.3g</td><td>%s</td></tr>", e.getIndex(), e.getOriginNode().getIndex() , e.getOriginNode().getName(), e.getDestinationNode().getIndex(),e.getDestinationNode().getName(), T_e_prop[linkId], T_e_tx[linkId], T_e_buf[linkId], T_e[linkId], e.getAttributes())); 130 } 131 out.append("</table>"); 132 133 // Route information table 134 out.append("<h2>Path delay information</h2>"); 135 out.append("<table border='1'>"); 136 out.append("<tr><th><b>Route id</a></b></th><th><b>Demand id</a></b></th><th><b>Ingress node</b></th><th><b>Egress node</b></th><th><b>Sequence of links</b></th><th><b>Propagation delay (ms)</b></th><th><b>Transmission delay (ms)</b></th><th><b>Queuing delay (ms)</b></th><th><b>Total delay (ms)</b></th><th><b>Attributes</a></b></th></tr>"); 137 for (Route r : netPlan.getRoutes()) 138 { 139 final int rIndex = r.getIndex(); 140 final Demand d = r.getDemand(); 141 out.append(String.format("<tr><td>%d</td><td>%d</td><td>%d (%s)</td><td>%d (%s)</td><td>%s</td><td>%.3g</td><td>%.3g</td><td>%.3g</td><td>%.3g</td><td>%s</td></tr>", r.getIndex () , d.getIndex(), r.getIngressNode().getIndex() , r.getIngressNode().getName(), r.getEgressNode().getIndex() , r.getEgressNode().getName(), r.getSeqLinks(), T_r_prop[rIndex], T_r_tx[rIndex], T_r_buf[rIndex], T_r[rIndex], r.getAttributes())); 142 } 143 out.append("</table>"); 144 145 // Demand information table 146 out.append("<h2>Demand delay information</h2>"); 147 out.append("<table border='1'>"); 148 out.append("<tr><th><b>Demand id</a></b></th><th><b>Ingress node</b></th><th><b>Egress node</b></th><th><b>Propagation delay (ms)</b></th><th><b>Transmission delay (ms)</b></th><th><b>Queuing delay (ms)</b></th><th><b>Total delay (ms)</b></th><th><b>Attributes</a></b></th></tr>"); 149 for (Demand d : netPlan.getDemands()) 150 { 151 final int dIndex = d.getIndex(); 152 out.append(String.format("<tr><td>%d</td><td>%d (%s)</td><td>%d (%s)</td><td>%.3g</td><td>%.3g</td><td>%.3g</td><td>%.3g</td><td>%s</td></tr>", dIndex, d.getIngressNode().getIndex() , d.getIngressNode().getName(), d.getEgressNode().getIndex() , d.getEgressNode().getName(), T_d_prop[dIndex] , T_d_tx[dIndex] , T_d_buf[dIndex] , T_d[dIndex] , d.getAttributes())); 153 } 154 out.append("</table>"); 155 156 // Network information table 157 out.append("<table border='1'>"); 158 out.append("<tr><td>Average network delay (ms) [UNICAST]</td><td>").append(String.format("%.3g", avNetDelay_T * 1000)).append("</td></tr>"); 159 out.append("<tr><td>Average network delay only considering propagation (ms) [UNICAST]</td><td>").append(String.format("%.3g", avNetDelay_T_prop * 1000)).append("</td></tr>"); 160 out.append("</table>"); 161 162 out.append("</body></html>"); 163 164 return out.toString(); 165 } 166 167 @Override 168 public String getDescription() 169 { 170 return "This report shows delay information considering a packet-switched network"; 171 } 172 173 @Override 174 public String getTitle() 175 { 176 return "Delay metrics"; 177 } 178 179 @Override 180 public List<Triple<String, String, String>> getParameters() 181 { 182 /* Returns the parameter information for all the InputParameter objects defined in this object (uses Java reflection) */ 183 return InputParameter.getInformationAllInputParameterFieldsOfObject(this); 184 } 185 186 187 188 189}