이 논문은 파장 분할 방식을 이용한 광 통신망에서 패킷 전송예약 문제를 다루었다. 통신망은 고정 주파수 수신기와 조절 가능한 송신기를 갖는 모델을 가정했다. 송신기의 레이저는 전체 통신 대역폭이 아닌 제한된 대역폭 내에서 조절 가능한 것을 가정하였다. 따라서 단일 홉 통신망을 만들기 위해서는 각 노드가 복수개의 레이저 혹은 복수개의 광 필터를 장착하고 있어야 한다. 본 논문에서는 먼저 모두에서 모두로의 패킷 전송 문제를 분석하고 최적의 알고리즘을 구했다. 그 다음으로 무작위 통화 요구를 갖는 경우 이 문제가 강한 의미에서 NP-hard임을 보였고 리스트 스케줄링에 기초한 근사 알고리즘을 제안했다. 또한 이 알고리즘이 이론적인 성능 한계와 수치 해석적 방법을 통한 성능을 보였다. 이 결과들은 조절 지연시간, 채널의 수 레이저의 조절범위의 변화에 관계없이 적용 가능하다.
In this paper, we consider the problem of packet transmission in a wavelength division multiplexed(WDM) optical network. Our network model assumes that receivers are fixed-tuned and transmitters are tunable such that optical lasers assigned to transmitters have limited access to the network bandwidth: hence each node must be equipped with multiple optical lasers and/or multiple optical filters in order to maintain a single-hop network. We first analyze scheduling all-to-all packet transmissions and present optimum scheduling for all-to-all packet transmissions. We then extend the analysis to the case of arbitrary traffic demands. We show that the scheduling with arbitrary traffic demand is NP-hard. A heuristic algorithm based on list scheduling is presented. The upper bound so obtained is compared with the lower bound and provides performance guarantees with arbitrary demands. The result are applicable to arbitrary tuning delay, arbitrary number of wavelength channels and optical lasers of arbitrary tuning ranges.
