QLEAP.py

from qns.entity.node.app import Application
from topo import WaxManTopology, Node, Channel
from qns.simulator.simulator import Simulator
from qns.simulator.event import func_to_event
from qns.utils.rnd import set_seed
from qns.network.network import QuantumNetwork
import heapq
import numpy as np
import math
from typing import List, Tuple, Union
from qns.network.route import DijkstraRouteAlgorithm
from qns.network.topology.topo import ClassicTopology


def find_link(src: Node, dest: Node, net: QuantumNetwork) -> Union[Channel, None]:
    for channel in net.qchannels:
        if (channel.src == src and channel.dest == dest) or (channel.src == dest and channel.dest == src):
            return channel
    return None


def pur_fidelity(fidelity1: float, fidelity2: float) -> float:
    return (fidelity1 * fidelity2)/(fidelity1 * fidelity2 + (1 - fidelity1) * (1 - fidelity2))


class QLeap(Application):
    def __init__(self, network: QuantumNetwork, node: Node, request: Tuple[Node, Node], req_th: int, fth: float = 0.8, q = 0.5):
        super().__init__()
        self.node = node
        self.network = network
        self.request = request  # (src, dest)
        self.req_th = req_th
        self.fth = fth
        self.com = 0  # 资源消耗
        self.th = 0.0  # 吞吐量
        self.paths = []  # 储存找到的路径
        self.length = 0.0  # 储存路径总长度
        self.fi = 0.0  # 储存该路径的期望保真度
        self.path_th = []  # 储存该路径的吞吐量
        self.num_pur = []  # 储存纠缠次数
        self.used_capacity = []  # 储存纠缠消耗数
        self.resurce_use_rate = 0.0  # 资源利用率
        self.total_resurce = 0.0
        self.q = q  # 量子信道的损耗率

    def install(self, node: Node, simulator: Simulator):
        super().install(node, simulator)
        t = simulator.ts
        event = func_to_event(t, self.qleap, by=self)
        self._simulator.add_event(event)

    def calculte_pur_table(self, net: QuantumNetwork):
        # 计算网络中每条链路的提纯表
        for channel in net.qchannels:
            init_fidelity = fidelity = channel.init_fidelity
            pur_table = []
            pur_table.append((fidelity, 0.0))
            for i in range(1, channel.capacity):
                after_pur_fidelity = pur_fidelity(fidelity, init_fidelity)
                fidelity_up = after_pur_fidelity - fidelity
                pur_table.append((after_pur_fidelity, fidelity_up))
                fidelity = after_pur_fidelity
            channel.pur_table = pur_table

    def delete_link(self, net: QuantumNetwork):
        for channel in net.qchannels:
            if channel.pur_table:
                if channel.pur_table[-1][0] < self.fth:
                    channel.capacity = -1  # 删除该链路

    def dijkstra(self, net: QuantumNetwork, src: Node, dest: Node) -> Tuple[float, List[Node]]:
        # 扩展dijkstra算法寻路
        visted = []
        n = len(net.nodes)
        distances = [float('inf')]*n  # 初始化距离
        previous = [-1]*n
        fidelity = [1.0]*n

        # 起始节点
        distances[src.id] = 0.0

        # 使用最小堆
        heap = [(0.0, src.id)]  # (log(距离), 节点)

        while heap:
            current_log_dist, current_node_id = heapq.heappop(heap)
            current_node = net.nodes[current_node_id]

            if current_node in visted:
                continue
            visted.append(current_node)
            if current_node == dest:
                break

            for channel in net.qchannels:
                neighbor = None
                if channel.src == current_node:
                    neighbor = channel.dest
                elif channel.dest == current_node:
                    neighbor = channel.src
                else:
                    continue
                if neighbor in visted or channel.capacity < 1:
                    continue
                # 计算经过该链路后的距离
                new_log_dist = current_log_dist - math.log(channel.init_fidelity)
                if new_log_dist < distances[neighbor.id]:
                    fidelity[neighbor.id] = fidelity[current_node.id] * channel.init_fidelity
                    distances[neighbor.id] = new_log_dist
                    previous[neighbor.id] = current_node
                    heapq.heappush(heap, (new_log_dist, neighbor.id))

        # 构建路径
        path = []
        current_node = dest
        if previous[current_node.id] == -1 and current_node != src:
            return 0.0, []
        while current_node != -1:
            path.append(current_node)
            current_node = previous[current_node.id]
        path.reverse()

        return fidelity[dest.id], path

    def calulate_num_pur(self, net: QuantumNetwork, path: List[Node], fth_ave: float) -> List[int]:
        num_pur = []
        # 计算网络中每条链路的提纯表
        for i in range(len(path)-1):
            channel = find_link(path[i], path[i+1], net)
            if channel is None:
                print("Error: Channel not found")
                exit(1)
            fl = 0
            tmpf = channel.init_fidelity
            while tmpf < fth_ave and fl < channel.capacity - 1:
                fl += 1
                tmpf = channel.pur_table[fl][0]
            if tmpf >= fth_ave:
                num_pur.append(fl)
            else:
                num_pur.append(-1)  # 标记该路径不可用
        return num_pur

    def is_path_used(self, path: List[Node], num_pur: List[int]) -> bool:
        for i in range(len(path)-1):
            link = find_link(path[i], path[i+1], self.network)
            if num_pur[i] == -1:
                link.capacity = 0
            elif link.capacity < (num_pur[i] + 1):
                link.capacity = 0

    def calculate_path_fidelity(self, net: QuantumNetwork, path: List[Node], num_pur: List[int]) -> float:
        fidelity = 1.0
        for i in range(len(path)-1):
            channel = find_link(path[i], path[i+1], net)
            if channel is None:
                print("Error: Channel not found")
                exit(1)
            fidelity = (1/4+3/4*(4*fidelity-1)*(4*channel.pur_table[num_pur[i]][0]-1)/9)
        return fidelity

    def calculate_p_pur_link(self, channel: Channel, num_pur: int) -> float:
        if num_pur == 0:
            return 1.0
        init_fidelity = channel.init_fidelity
        succ = 1.0
        for i in range(num_pur):
            fidelity = channel.pur_table[i+1][0]
            succ *= fidelity * init_fidelity + (1 - fidelity) * (1 - init_fidelity)
        return succ

    def calculate_p_pur_path(self, net: QuantumNetwork, path: List[Node], num_pur: List[int]) -> float:
        capacity = 10000
        for i in range(len(path)-1):
            channel = find_link(path[i], path[i+1], net)
            if channel is None:
                print("Error: Channel not found")
                exit(1)
            succ_link = self.calculate_p_pur_link(channel, num_pur[i])
            channel_capacity = channel.capacity // (num_pur[i] + 1) * succ_link
            capacity = min(capacity, channel_capacity)
        return capacity

    def calculate_path_capacity(self, net: QuantumNetwork, path: List[Node], num_pur: List[int]) -> int:
        capacity = 10000
        for i in range(len(path)-1):
            channel = find_link(path[i], path[i+1], net)
            if channel is None:
                print("Error: Channel not found")
                exit(1)
            channel_capa = 0

            channel_capa = channel.capacity / (num_pur[i] + 1)
            capacity = min(capacity, channel_capa)
        return capacity

    def calculate_path_resource_com_and_delete_link(self, net: QuantumNetwork, path: List[Node], num_pur: List[int], used_capacity: int) -> int:
        com = 0
        tmp_capa1 = 10000
        for i in range(len(path) - 1):
            channel = find_link(path[i], path[i+1], self.network)
            tmp_capa1 = min(tmp_capa1, channel.capacity//(num_pur[i]+1))

        for i in range(len(path)-1):
            channel = find_link(path[i], path[i+1], net)
            if channel is None:
                print("Error: Channel not found")
                exit(1)
            com += (num_pur[i]+1) * tmp_capa1
            channel.capacity -= (num_pur[i]+1) * tmp_capa1
        return com

    def is_have_resurce(self, path: List[Node], num_pur: List[int]) -> bool:
        for i in range(len(path)-1):
            channel = find_link(path[i], path[i+1], self.network)
            if channel is None:
                print("Error: Channel not found")
                exit(1)
            if num_pur[i] == -1:
                return False
            if channel.capacity < (num_pur[i] + 1):
                return False
        return True

    def qleap(self):
        for link in self.network.qchannels:
            if link.capacity > 0:
                self.total_resurce += link.capacity
        src, dest = self.request
        self.calculte_pur_table(self.network)
        self.delete_link(self.network)
        while True:
            fidelity, path = self.dijkstra(self.network, src, dest)
            tmp_capa = 10000
            for i in range(len(path)-1):
                channel = find_link(path[i], path[i+1], self.network)
                if channel is None:
                    print("Error: Channel not found")
                    exit(1)
                tmp_capa = min(tmp_capa, channel.capacity)
            if tmp_capa < 1:
                break
            if path == []:
                break

            fth_ave = self.fth ** (1 / (len(path) - 1))
            fidelity = self.calculate_path_fidelity(self.network, path, [0]*(len(path)-1))
            if fidelity < self.fth:
                # 纯化决策
                num_pur = self.calulate_num_pur(self.network, path, fth_ave)
            else:
                num_pur = [0]*(len(path)-1)

            self.is_path_used(path, num_pur)

            if self.is_have_resurce(path, num_pur):
                for i in range(len(num_pur)):
                    if num_pur[i] == -1:
                        break
                self.num_pur.append(num_pur)
                self.paths.append(path)
                fidelity = self.calculate_path_fidelity(self.network, path, num_pur)

                path_capacity = self.calculate_p_pur_path(self.network, path, num_pur)
                
                self.length += path_capacity
                path_th = path_capacity * self.q**(len(path)-2)  # 考虑中继节点的延迟影响
                self.path_th.append(path_th)
                self.used_capacity.append(path_capacity)
                self.th += path_th
                self.fi += (fidelity * path_th)
                self.com += self.calculate_path_resource_com_and_delete_link(self.network, path, num_pur, path_capacity)
        if self.th > 0:
            self.fi = self.fi / self.th
        else:
            self.fi = 0.0
        self.resurce_use_rate = self.com / self.total_resurce if self.total_resurce > 0.0 else 0
        self.com = self.com / self.th if self.th > 0 else 0
        return self.path_th, self.fi


if __name__ == "__main__":
    end_sim_time = 10
    start_sim_time = 0
    accuracy = 1000000
    set_seed(42)
    nodes_number = 20
    fths = np.arange(0.52, 0.95, 0.1)
    times = []
    capa = 40
    th = []
    fi = []
    com = []
    
    num = 10
    for fth in fths:
        topo = WaxManTopology(num_nodes=nodes_number, capacity=capa)
        t = 0.0
        f = []
        c = []
        for i in range(num):
            print(f"Running simulation for nodes_number = {nodes_number} iteration {i+1}/{num}")
            s = Simulator(start_sim_time, end_sim_time, accuracy=accuracy)
            net = QuantumNetwork(name="network", topo=topo, route=DijkstraRouteAlgorithm(), classic_topo=ClassicTopology.All)

            node = net.nodes[-1]
            # print(node)
            src_id = 0
            dest_id = -1
            request = (net.nodes[src_id], net.nodes[dest_id])
            node.add_apps(QLeap(network=net, node=node, request=request, req_th=500, fth=fth, q=0.5))
            net.install(s)
            s.run()

            t += node.apps[0].th
            if node.apps[0].fi:
                f.append(node.apps[0].fi)
            if node.apps[0].com:
                c.append(node.apps[0].com)

        th.append(t / num)
        fi.append(sum(f) / len(f))
        com.append(sum(c) / len(c))
    print("Final Results:")
    print(f"Fidelities: {fi}")
    print(f"Throughputs: {th}")
    print(f"Times: {times}")

    for i in range(len(fths)):
        print(f"fth: {fths[i]:.2f}, Average Fidelity: {fi[i]:.3f}, Average Throughput: {th[i]:.2f}, Consum: {com[i]:.3f}")