1546:- The Impairment Aware Best Fit (IA-BF) algorithm was proposed in. This algorithm is a distributed approach that is dependent upon a large amount of communication to use global information to always pick the shortest available path and wavelength. This is accomplished through the use of serial multi-probing. The shortest available path and wavelength are attempted first, and upon failure, the second shortest available path and wavelength are attempted. This process continues until a successful path and wavelength have been found or all wavelengths have been attempted.
2161:
830:
The RWA problem is further complicated by the need to consider signal quality. Many of the optical impairments are nonlinear, so a standard shortest path algorithm can't be used to solve them optimally even if we know the exact state of the network. This is usually not a safe assumption, so solutions
977:
Fixed alternate routing is an extension of fixed path routing. Instead of having just one fixed route for a given source and destination pair, several routes are stored. The probes can be sent in a serial or parallel fashion. For each connection request, the source node attempts to find a connection
36:
The general objective of the RWA problem is to maximize the number of established connections. Each connection request must be given a route and wavelength. The wavelength must be consistent for the entire path, unless the usage of wavelength converters is assumed. Two connections requests can share
2140:
In the authors report on the algorithm which can be used to solve efficiently and optimally a constrained RWA problem. The authors study a constrained routing and spectrum assignment (RSA) problem, which can be reduced to a constrained RWA problem by requesting one slice. The constriction limits
2132:
The ILP formulation listed above can be solved using a traditional ILP solver. This is typically done by temporarily relaxing the integer constraints, solving the problem optimally, and converting the real solution to an integer solution. Additional constraints can be added and the process repeated
2112:
There are several other wavelength assignment algorithms: Least Used, Most Used, Min
Product, Least Loaded, Max Sum, and Relative Capacity Loss. Most Used outperforms Least Used use significantly, and slightly outperforms First Fit. Min Product, Least Loaded, Max Sum, and Relative Capacity Loss all
1463:
The physically aware backward reservation algorithm (PABR) is an extension of LORA. PABR is able to improve performance in two ways: considering physical impairments and improved wavelength selection. As PABR is searching for an optical path, paths with an unacceptable signal quality due to linear
1195:
The major issue with both fixed path routing and fixed alternate routing is that neither algorithm takes into account the current state of the network. If the predetermined paths are not available, the connection request will become blocked even though other paths may exist. Fixed Path
Routing and
2124:
An alternate approach to selecting a route and wavelength separately is to consider them jointly. These approaches tend to be more theoretical and not as practical. As this is an NP-complete problem, an exact solution is likely not possible. The approximation techniques usually aren't very useful
2035:
Two of the most common methods for wavelength assignment are First Fit and Random Fit. First Fit chooses the available wavelength with the lowest index. Random Fit determines which wavelengths are available and then chooses randomly amongst them. The complexity of both algorithms is
873:
The SP-1 (Shortest Path, 1 Probe) algorithm is an example of a Fixed Path
Routing solution. This algorithm calculates the shortest path using the number of optical routers as the cost function. A single probe is used to establish the connection using the shortest path. The
2088:
An extension to First Fit and Random Fit was proposed in to consider signal quality. Quality First Fit and
Quality Random Fit eliminate from consideration wavelengths which have an unacceptable signal quality. The complexity of these algorithms is higher though, as up to
1471:
PABR also considers signal quality when making the wavelength selection. It accomplishes this by removing from consideration all wavelengths with an unacceptable signal quality level. The approach is called
Quality First Fit and it is discussed in the following section.
1211:(LORA) algorithm was proposed in. The main idea behind LORA is to route connection requests away from congested areas of the network, increasing the probability that connection requests will be accepted. This is accomplished by setting the cost of each link to be
2144:
In the authors report on the generalized
Dijkstra algorithm, which can be used to efficiently and optimally solve the RWA, RSA, and the routing, modulation, and spectrum assignment (RMSA) problems, without the limit on the path length.
865:
Fixed path routing is the simplest approach to finding a lightpath. The same fixed route for a given source and destination pair is always used. Typically this path is computed ahead of time using a shortest path algorithm, such as
1196:
Fixed
Alternate Routing are both not quality aware. For these reasons, most of the research in RWA is currently taking place in Adaptive algorithms. Five examples of Adaptive Routing are LORA, PABR, IA-BF, IA-FF, and AQoS.
1634:. The purpose of each counter is to determine which issue is a bigger factor in blocking: Path and wavelength availability or Quality requirements. The algorithm chooses routes differently based upon the larger issue.
1467:
Note that PABR can only consider linear impairments. The nonlinear impairments, on the other hand, would not be possible to estimate in a distributed environment due to their requirement of global traffic knowledge.
1817:
870:. While this approach is very simple, the performance is usually not sufficient. If resources along the fixed path are in use, future connection requests will be blocked even though other paths may exist.
140:
368:
843:
The first method is solving the routing portion first, and then assigning a wavelength second. Three types of route selection are Fixed Path
Routing, Fixed Alternate Routing, and Adaptive Routing.
555:
251:
1199:
Adaptive algorithms fall into two categories: traditional and physically aware. Traditional adaptive algorithms do not consider signal quality, however, physically aware adaptive algorithms do.
1559:
of IA-BF. Instead of picking the wavelengths in terms of the minimum cost, the wavelengths are selected in order according to their index. IA-BF tends to outperform IA-FF under most scenarios.
2116:
A significant disadvantage of these algorithms is that they require a significant communication overhead, making them unpractical to implement unless you have a centralized network structure.
2173:
I. Chlamtac, A. Ganz, and G. Karmi, "Lightpath communications: an approach to high bandwidth optical WAN's," {\it IEEE Transactions on
Communications}, Vol 40, No 7, pp. 1171-1182, July 1992.
1535:. With single-probing, only one path is selected by the route selection. With multi-probing, multiple paths are attempted in parallel, increasing the probability of connection success.
1281:
418:
465:
1125:
716:
1962:
1918:
1549:
The multi-probing approach will allow IA-BF to outperform both PABR-1 and LORA-1. However, as the number of probes increases, the performance of the algorithms is similar.
920:
780:
748:
2027:
This algorithm is single probing approach. The multi-probing approach, which the paper names ALT-AQoS (alternate AQoS) is a simple extension upon the same basic idea.
1632:
1342:
1596:
2022:
1992:
1874:
1669:
1453:
1429:
1409:
1389:
1301:
1045:
587:
1844:
614:
2063:
2107:
2083:
1533:
1513:
1493:
1362:
1185:
1165:
1145:
1065:
1019:
999:
960:
940:
814:
674:
654:
634:
2248:
2252:
2238:
R. Barry and S. Subramaniam, "The MAX-SUM Wavelength
Assignment Algorithm for WDM Ring Networks," Proceedings of Optical Fiber Conference, February 1997.
2182:
S. Evan, A. Itai, and A. Shamir, "On the Complexity of Timetable and Multicommodity Flow Problems," SIAM Journal on Computing, Vol 5, pp 691-703, 1976
978:
on each of the paths. If all of the paths fail, then the connection is blocked. If multiple paths are available, only one of them would be utilized.
1565:- Adaptive Quality of Service (AQoS) was proposed in. This algorithm is unique in a couple of ways. First, each node maintains two counters:
2229:
T. Deng and S. Subramaniam, "Adaptive QoS Routing in Dynamic Wavelength-Routed Optical Networks," Broadband Networks 2005, pp. 184-193, 2005
789:. This type of problem is known as Static Lightpath Establishment (SLE). The above formulation also does not consider the signal quality.
2296:
2125:
either, as they will require centralized control and, usually, predefined traffic demands. Two joint approaches are ILP formulation and
1674:
820:
of a general graph. Given that dynamic RWA is more complex than static RWA, it must be the case that dynamic RWA is also NP-complete.
2301:
59:
257:
471:
2306:
2217:
153:
969:
as the cost function. The SP-1 algorithm could be extended to use different cost functions, such as the number of EDFAs.
824:
2207:
W. Lin, "Physically Aware Agile Optical Networks," Ph.D. Dissertation, Montana State University, Bozeman, July 2008.
2218:
Connection Provisioning With Transmission Impairment Consideration in Optical WDM Networks With High-Speed Channels
25:
1475:
Both LORA and PABR can be implemented with either single-probing or multi-probing. The maximum number of probes
1368:
to broadcast recent usage information periodically. Note that LORA does not consider any physical impairments.
1214:
374:
867:
875:
424:
2192:
1074:
816:-graph colorability problem. In other words, solving the SLE RWA problem is as complex as finding the
679:
2268:", Proceedings of the 20th Optical Network Design and Modeling Conference, Cartagena, Spain, May 2016
2162:
A Review of Routing and Wavelength Assignment Approaches for Wavelength Routed Optical WDM Networks
1923:
1879:
881:
753:
721:
45:
2113:
try to choose a wavelength that minimizes the probability that future requests will be blocked.
2024:
link, respectively. The repeated quality factor estimations are computationally very expensive.
1068:
1067:
shortest paths using the number of optical routers as the cost function. The running time using
2195:." 4OR–Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 2003
962:
is the number of routers. The running time is just a constant if a predetermined path is used.
1601:
1391:
is equal to one, the LORA algorithm is identical to the SP algorithm. Increasing the value of
1306:
1568:
2134:
1997:
1967:
1849:
1644:
1556:
1464:
impairments are pruned. In other words, PABR is LORA with an additional quality constraint.
1438:
1414:
1394:
1374:
1286:
1187:
is the number of paths. The running time is a constant factor if the paths are precomputed.
1024:
562:
1822:
1364:. A standard shortest path algorithm can then be used to find the path. This requires each
592:
2039:
846:
The second approach is to consider both route selection and wavelength assignment jointly.
839:
Given the complexity of RWA, there are two general methodologies for solving the problem:
2126:
2092:
2068:
1518:
1498:
1478:
1365:
1347:
1170:
1150:
1130:
1050:
1004:
984:
945:
925:
817:
799:
659:
639:
619:
2290:
1432:
1047:) algorithm is an example of Fixed Alternate Routing. This algorithm calculates the
38:
2265:
1303:
is parameter that can be dynamically adjusted according to the traffic load and
793:
823:
Another NP-complete proof is given in. This proof involves a reduction to the
966:
785:
Note that the above formulation assumes that the traffic demands are known
616:
is the number of connections established for each source-destination pair.
1638:
1208:
28:
problem with the goal of maximizing the number of optical connections.
1411:
will increase the bias towards less used routes. The optimal value of
2277:
Ireneusz Szcześniak, Andrzej Jajszczyk and Bożena Woźna-Szcześniak, "
2249:
Wavelength Assignment for Dynamic Traffic in Multi-Fiber WDM Networks
2278:
718:
is a matrix which shows which source-destination pairs are active,
2085:
is the number of wavelengths. First Fit outperforms Random Fit.
1812:{\displaystyle D_{i}={\frac {\sum _{j=1}^{N_{i}}10\log}{N_{i}}}}
2193:
A new implementation of Yen's ranking loopless paths algorithm
2266:
Adapted and Constrained Dijkstra for Elastic Optical Networks
2220:," Journal of Lightwave Technology, Vol 23, No 3, March 2005.
831:
need to be efficient using only limited network information.
135:{\displaystyle C_{0}(\rho ,q)=\sum _{i=1}^{N_{sd}}m_{i}}
363:{\displaystyle c_{ij}\in {0,1},i=1,2,...,P,j=1,2,...,W}
2095:
2071:
2042:
2000:
1994:
lightpath at the source and destination nodes of the
1970:
1926:
1882:
1852:
1825:
1677:
1647:
1604:
1571:
1521:
1501:
1481:
1441:
1417:
1397:
1377:
1350:
1309:
1289:
1217:
1173:
1153:
1133:
1077:
1053:
1027:
1007:
987:
948:
928:
884:
802:
756:
724:
682:
662:
642:
622:
595:
565:
550:{\displaystyle m_{i}\leq q_{i}\rho ,i=1,2,...,N_{sd}}
474:
427:
377:
260:
156:
62:
48:(ILP). The ILP formulation given here is taken from.
750:
is a matrix which shows which links are active, and
246:{\displaystyle m_{i}\geq 0,integer,i=1,2,...,N_{sd}}
2264:Ireneusz Szcześniak and Bożena Woźna-Szcześniak, "
2101:
2077:
2057:
2016:
1986:
1956:
1912:
1868:
1838:
1811:
1663:
1626:
1590:
1527:
1507:
1487:
1447:
1423:
1403:
1383:
1356:
1336:
1295:
1275:
1179:
1159:
1139:
1119:
1059:
1039:
1013:
993:
954:
934:
914:
808:
774:
742:
710:
668:
648:
628:
608:
581:
549:
459:
412:
362:
245:
134:
2164:," {\it Optical Networks Magazine}, January 2000.
589:is the number of source-destination pairs, while
792:It has been shown that the SLE RWA problem is
44:The RWA problem can be formally defined in an
2203:
2201:
2109:calls to estimate the Q-factor are required.
782:is a route and wavelength assignment matrix.
8:
1344:is the number of wavelengths in use on link
1964:are the quality factor measurements of the
41:, provided a different wavelength is used.
2253:International Conference on Communications
2216:Y. Huang, J. Heritage, and B. Mukherjee, "
1637:Another distinction is that AQoS uses the
1555:- Impairment Aware First Fit (IA-FF) is a
1455:were between 1.1 and 1.2 in the proposal.
796:in. The proof involves a reduction to the
676:is the set of paths to route connections.
2094:
2070:
2041:
2005:
1999:
1975:
1969:
1942:
1931:
1925:
1898:
1887:
1881:
1857:
1851:
1830:
1824:
1801:
1781:
1770:
1761:
1749:
1738:
1714:
1709:
1698:
1691:
1682:
1676:
1652:
1646:
1609:
1603:
1576:
1570:
1520:
1500:
1480:
1440:
1416:
1396:
1376:
1349:
1308:
1288:
1276:{\displaystyle cost(l)=\beta ^{usage(l)}}
1246:
1216:
1172:
1152:
1132:
1076:
1052:
1026:
1006:
986:
947:
927:
883:
851:First routing, then wavelength assignment
801:
755:
723:
699:
681:
661:
641:
621:
600:
594:
570:
564:
538:
492:
479:
473:
448:
438:
426:
398:
382:
376:
277:
265:
259:
234:
161:
155:
126:
111:
106:
95:
67:
61:
413:{\displaystyle C^{T}B\leq l_{W\times L}}
2153:
2120:Joint routing and wavelength assignment
1431:can be calculated using the well-known
2279:Generic Dijkstra for Optical Networks
878:is the cost of Dijkstra's algorithm:
7:
2160:H. Zang, J. Jue, and B. Mukherjee, "
1846:is the number of lightpaths on the
1671:link is calculated by this formula
1641:as the link cost. The cost of the
14:
1435:algorithm. The optimal values of
965:This definition of SP-1 uses the
460:{\displaystyle m\leq 1_{W}C^{T}A}
18:routing and wavelength assignment
1120:{\displaystyle O(pn(m+n\log n))}
711:{\displaystyle A:P\times N_{sd}}
2255:, Vol 1, pp 406-410, June 1997.
2052:
2046:
1949:
1943:
1905:
1899:
1793:
1788:
1782:
1756:
1750:
1731:
1331:
1325:
1268:
1262:
1236:
1230:
1167:is the number of routers, and
1114:
1111:
1090:
1081:
909:
888:
656:is the number of wavelengths.
85:
73:
1:
1957:{\displaystyle Q_{i,j}^{(d)}}
1913:{\displaystyle Q_{i,j}^{(s)}}
1459:Physically aware adaptive RWA
2191:M. Pascoal and E. Martins. "
915:{\displaystyle O(m+n\log n)}
825:Multi-commodity Flow Problem
942:is the number of edges and
775:{\displaystyle C:P\times W}
743:{\displaystyle B:P\times L}
636:is the number of links and
2323:
2297:Fiber-optic communications
2302:Telecommunication theory
1627:{\displaystyle N_{wave}}
1539:Other routing approaches
1337:{\displaystyle usage(l)}
1203:Traditional adaptive RWA
1147:is the number of edges,
2247:X. Zhang and C. Qiao, "
1591:{\displaystyle N_{BER}}
973:Fixed alternate routing
2103:
2079:
2059:
2018:
2017:{\displaystyle i_{th}}
1988:
1987:{\displaystyle j_{th}}
1958:
1914:
1870:
1869:{\displaystyle i_{th}}
1840:
1813:
1721:
1665:
1664:{\displaystyle i_{th}}
1628:
1592:
1529:
1509:
1489:
1449:
1448:{\displaystyle \beta }
1425:
1424:{\displaystyle \beta }
1405:
1404:{\displaystyle \beta }
1385:
1384:{\displaystyle \beta }
1358:
1338:
1297:
1296:{\displaystyle \beta }
1277:
1181:
1161:
1141:
1121:
1061:
1041:
1040:{\displaystyle p>1}
1015:
995:
956:
936:
916:
810:
776:
744:
712:
670:
650:
630:
610:
583:
582:{\displaystyle N_{sd}}
551:
461:
414:
364:
247:
136:
121:
46:integer linear program
2133:indefinitely using a
2104:
2080:
2060:
2031:Wavelength assignment
2019:
1989:
1959:
1915:
1871:
1841:
1839:{\displaystyle N_{i}}
1814:
1694:
1666:
1629:
1593:
1530:
1510:
1490:
1450:
1426:
1406:
1386:
1359:
1339:
1298:
1278:
1182:
1162:
1142:
1122:
1062:
1042:
1016:
996:
957:
937:
917:
811:
777:
745:
713:
671:
651:
631:
611:
609:{\displaystyle m_{i}}
584:
552:
462:
415:
365:
248:
137:
91:
2307:NP-complete problems
2093:
2069:
2058:{\displaystyle O(w)}
2040:
1998:
1968:
1924:
1880:
1850:
1823:
1675:
1645:
1602:
1569:
1519:
1499:
1479:
1439:
1415:
1395:
1375:
1348:
1307:
1287:
1215:
1207:The lexicographical
1171:
1151:
1131:
1075:
1051:
1025:
1005:
985:
946:
926:
882:
868:Dijkstra's Algorithm
800:
754:
722:
680:
660:
640:
620:
593:
563:
472:
425:
375:
258:
154:
60:
1953:
1909:
1792:
1760:
1495:is denoted as LORA-
2251:," Proceedings of
2099:
2075:
2055:
2014:
1984:
1954:
1927:
1910:
1883:
1866:
1836:
1809:
1766:
1734:
1661:
1624:
1588:
1525:
1505:
1485:
1445:
1421:
1401:
1381:
1354:
1334:
1293:
1273:
1177:
1157:
1137:
1117:
1057:
1037:
1011:
991:
952:
932:
912:
861:Fixed path routing
856:Routing algorithms
806:
772:
740:
708:
666:
646:
626:
606:
579:
547:
457:
410:
360:
243:
132:
26:optical networking
2141:the path length.
2102:{\displaystyle w}
2078:{\displaystyle w}
1807:
1528:{\displaystyle p}
1508:{\displaystyle p}
1488:{\displaystyle p}
1357:{\displaystyle l}
1209:routing algorithm
1180:{\displaystyle p}
1160:{\displaystyle n}
1140:{\displaystyle m}
1060:{\displaystyle p}
1014:{\displaystyle p}
994:{\displaystyle p}
955:{\displaystyle n}
935:{\displaystyle m}
809:{\displaystyle n}
669:{\displaystyle P}
649:{\displaystyle W}
629:{\displaystyle L}
2314:
2282:
2275:
2269:
2262:
2256:
2245:
2239:
2236:
2230:
2227:
2221:
2214:
2208:
2205:
2196:
2189:
2183:
2180:
2174:
2171:
2165:
2158:
2135:branch and bound
2108:
2106:
2105:
2100:
2084:
2082:
2081:
2076:
2064:
2062:
2061:
2056:
2023:
2021:
2020:
2015:
2013:
2012:
1993:
1991:
1990:
1985:
1983:
1982:
1963:
1961:
1960:
1955:
1952:
1941:
1919:
1917:
1916:
1911:
1908:
1897:
1875:
1873:
1872:
1867:
1865:
1864:
1845:
1843:
1842:
1837:
1835:
1834:
1818:
1816:
1815:
1810:
1808:
1806:
1805:
1796:
1791:
1780:
1765:
1759:
1748:
1720:
1719:
1718:
1708:
1692:
1687:
1686:
1670:
1668:
1667:
1662:
1660:
1659:
1633:
1631:
1630:
1625:
1623:
1622:
1597:
1595:
1594:
1589:
1587:
1586:
1557:simple extension
1534:
1532:
1531:
1526:
1514:
1512:
1511:
1506:
1494:
1492:
1491:
1486:
1454:
1452:
1451:
1446:
1430:
1428:
1427:
1422:
1410:
1408:
1407:
1402:
1390:
1388:
1387:
1382:
1363:
1361:
1360:
1355:
1343:
1341:
1340:
1335:
1302:
1300:
1299:
1294:
1282:
1280:
1279:
1274:
1272:
1271:
1191:Adaptive routing
1186:
1184:
1183:
1178:
1166:
1164:
1163:
1158:
1146:
1144:
1143:
1138:
1126:
1124:
1123:
1118:
1066:
1064:
1063:
1058:
1046:
1044:
1043:
1038:
1020:
1018:
1017:
1012:
1001:(Shortest Path,
1000:
998:
997:
992:
961:
959:
958:
953:
941:
939:
938:
933:
921:
919:
918:
913:
818:chromatic number
815:
813:
812:
807:
781:
779:
778:
773:
749:
747:
746:
741:
717:
715:
714:
709:
707:
706:
675:
673:
672:
667:
655:
653:
652:
647:
635:
633:
632:
627:
615:
613:
612:
607:
605:
604:
588:
586:
585:
580:
578:
577:
556:
554:
553:
548:
546:
545:
497:
496:
484:
483:
466:
464:
463:
458:
453:
452:
443:
442:
419:
417:
416:
411:
409:
408:
387:
386:
369:
367:
366:
361:
287:
273:
272:
252:
250:
249:
244:
242:
241:
166:
165:
141:
139:
138:
133:
131:
130:
120:
119:
118:
105:
72:
71:
24:) problem is an
2322:
2321:
2317:
2316:
2315:
2313:
2312:
2311:
2287:
2286:
2285:
2281:", October 2018
2276:
2272:
2263:
2259:
2246:
2242:
2237:
2233:
2228:
2224:
2215:
2211:
2206:
2199:
2190:
2186:
2181:
2177:
2172:
2168:
2159:
2155:
2151:
2122:
2091:
2090:
2067:
2066:
2038:
2037:
2033:
2001:
1996:
1995:
1971:
1966:
1965:
1922:
1921:
1878:
1877:
1853:
1848:
1847:
1826:
1821:
1820:
1797:
1710:
1693:
1678:
1673:
1672:
1648:
1643:
1642:
1605:
1600:
1599:
1572:
1567:
1566:
1541:
1517:
1516:
1497:
1496:
1477:
1476:
1461:
1437:
1436:
1413:
1412:
1393:
1392:
1373:
1372:
1346:
1345:
1305:
1304:
1285:
1284:
1242:
1213:
1212:
1205:
1193:
1169:
1168:
1149:
1148:
1129:
1128:
1073:
1072:
1069:Yen's algorithm
1049:
1048:
1023:
1022:
1003:
1002:
983:
982:
975:
944:
943:
924:
923:
880:
879:
863:
858:
853:
837:
798:
797:
752:
751:
720:
719:
695:
678:
677:
658:
657:
638:
637:
618:
617:
596:
591:
590:
566:
561:
560:
534:
488:
475:
470:
469:
444:
434:
423:
422:
394:
378:
373:
372:
261:
256:
255:
230:
157:
152:
151:
122:
107:
63:
58:
57:
34:
12:
11:
5:
2320:
2318:
2310:
2309:
2304:
2299:
2289:
2288:
2284:
2283:
2270:
2257:
2240:
2231:
2222:
2209:
2197:
2184:
2175:
2166:
2152:
2150:
2147:
2127:Island Hopping
2121:
2118:
2098:
2074:
2054:
2051:
2048:
2045:
2032:
2029:
2011:
2008:
2004:
1981:
1978:
1974:
1951:
1948:
1945:
1940:
1937:
1934:
1930:
1907:
1904:
1901:
1896:
1893:
1890:
1886:
1863:
1860:
1856:
1833:
1829:
1804:
1800:
1795:
1790:
1787:
1784:
1779:
1776:
1773:
1769:
1764:
1758:
1755:
1752:
1747:
1744:
1741:
1737:
1733:
1730:
1727:
1724:
1717:
1713:
1707:
1704:
1701:
1697:
1690:
1685:
1681:
1658:
1655:
1651:
1621:
1618:
1615:
1612:
1608:
1585:
1582:
1579:
1575:
1540:
1537:
1524:
1504:
1484:
1460:
1457:
1444:
1420:
1400:
1380:
1366:optical switch
1353:
1333:
1330:
1327:
1324:
1321:
1318:
1315:
1312:
1292:
1270:
1267:
1264:
1261:
1258:
1255:
1252:
1249:
1245:
1241:
1238:
1235:
1232:
1229:
1226:
1223:
1220:
1204:
1201:
1192:
1189:
1176:
1156:
1136:
1116:
1113:
1110:
1107:
1104:
1101:
1098:
1095:
1092:
1089:
1086:
1083:
1080:
1056:
1036:
1033:
1030:
1010:
990:
974:
971:
951:
931:
911:
908:
905:
902:
899:
896:
893:
890:
887:
862:
859:
857:
854:
852:
849:
848:
847:
844:
836:
833:
805:
771:
768:
765:
762:
759:
739:
736:
733:
730:
727:
705:
702:
698:
694:
691:
688:
685:
665:
645:
625:
603:
599:
576:
573:
569:
558:
557:
544:
541:
537:
533:
530:
527:
524:
521:
518:
515:
512:
509:
506:
503:
500:
495:
491:
487:
482:
478:
467:
456:
451:
447:
441:
437:
433:
430:
420:
407:
404:
401:
397:
393:
390:
385:
381:
370:
359:
356:
353:
350:
347:
344:
341:
338:
335:
332:
329:
326:
323:
320:
317:
314:
311:
308:
305:
302:
299:
296:
293:
290:
286:
283:
280:
276:
271:
268:
264:
253:
240:
237:
233:
229:
226:
223:
220:
217:
214:
211:
208:
205:
202:
199:
196:
193:
190:
187:
184:
181:
178:
175:
172:
169:
164:
160:
143:
142:
129:
125:
117:
114:
110:
104:
101:
98:
94:
90:
87:
84:
81:
78:
75:
70:
66:
33:
30:
13:
10:
9:
6:
4:
3:
2:
2319:
2308:
2305:
2303:
2300:
2298:
2295:
2294:
2292:
2280:
2274:
2271:
2267:
2261:
2258:
2254:
2250:
2244:
2241:
2235:
2232:
2226:
2223:
2219:
2213:
2210:
2204:
2202:
2198:
2194:
2188:
2185:
2179:
2176:
2170:
2167:
2163:
2157:
2154:
2148:
2146:
2142:
2138:
2136:
2130:
2128:
2119:
2117:
2114:
2110:
2096:
2086:
2072:
2049:
2043:
2030:
2028:
2025:
2009:
2006:
2002:
1979:
1976:
1972:
1946:
1938:
1935:
1932:
1928:
1902:
1894:
1891:
1888:
1884:
1861:
1858:
1854:
1831:
1827:
1802:
1798:
1785:
1777:
1774:
1771:
1767:
1762:
1753:
1745:
1742:
1739:
1735:
1728:
1725:
1722:
1715:
1711:
1705:
1702:
1699:
1695:
1688:
1683:
1679:
1656:
1653:
1649:
1640:
1635:
1619:
1616:
1613:
1610:
1606:
1583:
1580:
1577:
1573:
1564:
1560:
1558:
1554:
1550:
1547:
1545:
1538:
1536:
1522:
1502:
1482:
1473:
1469:
1465:
1458:
1456:
1442:
1434:
1433:hill climbing
1418:
1398:
1378:
1369:
1367:
1351:
1328:
1322:
1319:
1316:
1313:
1310:
1290:
1265:
1259:
1256:
1253:
1250:
1247:
1243:
1239:
1233:
1227:
1224:
1221:
1218:
1210:
1202:
1200:
1197:
1190:
1188:
1174:
1154:
1134:
1108:
1105:
1102:
1099:
1096:
1093:
1087:
1084:
1078:
1070:
1054:
1034:
1031:
1028:
1008:
988:
979:
972:
970:
968:
963:
949:
929:
906:
903:
900:
897:
894:
891:
885:
877:
871:
869:
860:
855:
850:
845:
842:
841:
840:
834:
832:
828:
826:
821:
819:
803:
795:
790:
788:
783:
769:
766:
763:
760:
757:
737:
734:
731:
728:
725:
703:
700:
696:
692:
689:
686:
683:
663:
643:
623:
601:
597:
574:
571:
567:
542:
539:
535:
531:
528:
525:
522:
519:
516:
513:
510:
507:
504:
501:
498:
493:
489:
485:
480:
476:
468:
454:
449:
445:
439:
435:
431:
428:
421:
405:
402:
399:
395:
391:
388:
383:
379:
371:
357:
354:
351:
348:
345:
342:
339:
336:
333:
330:
327:
324:
321:
318:
315:
312:
309:
306:
303:
300:
297:
294:
291:
288:
284:
281:
278:
274:
269:
266:
262:
254:
238:
235:
231:
227:
224:
221:
218:
215:
212:
209:
206:
203:
200:
197:
194:
191:
188:
185:
182:
179:
176:
173:
170:
167:
162:
158:
150:
149:
148:
147:
127:
123:
115:
112:
108:
102:
99:
96:
92:
88:
82:
79:
76:
68:
64:
56:
55:
54:
53:
49:
47:
42:
40:
31:
29:
27:
23:
19:
2273:
2260:
2243:
2234:
2225:
2212:
2187:
2178:
2169:
2156:
2143:
2139:
2131:
2123:
2115:
2111:
2087:
2034:
2026:
1636:
1562:
1561:
1552:
1551:
1548:
1543:
1542:
1474:
1470:
1466:
1462:
1370:
1206:
1198:
1194:
980:
976:
964:
876:running time
872:
864:
838:
829:
822:
791:
786:
784:
559:
145:
144:
51:
50:
43:
39:optical link
35:
21:
17:
15:
835:Methodology
794:NP-complete
2291:Categories
2149:References
2137:approach.
146:subject to
52:Maximize:
32:Definition
1729:
1696:∑
1443:β
1419:β
1399:β
1379:β
1291:β
1244:β
1106:
967:hop count
904:
767:×
735:×
693:×
499:ρ
486:≤
432:≤
403:×
392:≤
275:∈
168:≥
93:∑
77:ρ
37:the same
2065:, where
1639:Q-factor
1515:or PABR-
1021:Probes,
922:, where
787:a priori
981:The SP-
1876:link,
1819:where
1283:where
1127:where
1553:IA-FF
1544:IA-BF
1371:When
1920:and
1598:and
1563:AQoS
1032:>
16:The
1726:log
1103:log
1071:is
901:log
22:RWA
2293::
2200:^
2129:.
1723:10
827:.
2097:w
2073:w
2053:)
2050:w
2047:(
2044:O
2010:h
2007:t
2003:i
1980:h
1977:t
1973:j
1950:)
1947:d
1944:(
1939:j
1936:,
1933:i
1929:Q
1906:)
1903:s
1900:(
1895:j
1892:,
1889:i
1885:Q
1862:h
1859:t
1855:i
1832:i
1828:N
1803:i
1799:N
1794:]
1789:)
1786:d
1783:(
1778:j
1775:,
1772:i
1768:Q
1763:/
1757:)
1754:s
1751:(
1746:j
1743:,
1740:i
1736:Q
1732:[
1716:i
1712:N
1706:1
1703:=
1700:j
1689:=
1684:i
1680:D
1657:h
1654:t
1650:i
1620:e
1617:v
1614:a
1611:w
1607:N
1584:R
1581:E
1578:B
1574:N
1523:p
1503:p
1483:p
1352:l
1332:)
1329:l
1326:(
1323:e
1320:g
1317:a
1314:s
1311:u
1269:)
1266:l
1263:(
1260:e
1257:g
1254:a
1251:s
1248:u
1240:=
1237:)
1234:l
1231:(
1228:t
1225:s
1222:o
1219:c
1175:p
1155:n
1135:m
1115:)
1112:)
1109:n
1100:n
1097:+
1094:m
1091:(
1088:n
1085:p
1082:(
1079:O
1055:p
1035:1
1029:p
1009:p
989:p
950:n
930:m
910:)
907:n
898:n
895:+
892:m
889:(
886:O
804:n
770:W
764:P
761::
758:C
738:L
732:P
729::
726:B
704:d
701:s
697:N
690:P
687::
684:A
664:P
644:W
624:L
602:i
598:m
575:d
572:s
568:N
543:d
540:s
536:N
532:,
529:.
526:.
523:.
520:,
517:2
514:,
511:1
508:=
505:i
502:,
494:i
490:q
481:i
477:m
455:A
450:T
446:C
440:W
436:1
429:m
406:L
400:W
396:l
389:B
384:T
380:C
358:W
355:,
352:.
349:.
346:.
343:,
340:2
337:,
334:1
331:=
328:j
325:,
322:P
319:,
316:.
313:.
310:.
307:,
304:2
301:,
298:1
295:=
292:i
289:,
285:1
282:,
279:0
270:j
267:i
263:c
239:d
236:s
232:N
228:,
225:.
222:.
219:.
216:,
213:2
210:,
207:1
204:=
201:i
198:,
195:r
192:e
189:g
186:e
183:t
180:n
177:i
174:,
171:0
163:i
159:m
128:i
124:m
116:d
113:s
109:N
103:1
100:=
97:i
89:=
86:)
83:q
80:,
74:(
69:0
65:C
20:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.