Routing Distributed

Definition of Distributed Routing protocol.

This module defines the DistributedRoutingProtocol, which is an OSPF-like routing protocol for quantum networks. Also included are the message types, packets, FSM, LSDB used by the routing protocol

class sequence.network_management.routing_distributed.DBDPayload(sender: str, summaries: list[LSAHeader])

Database Description payload.

sender

name of sender node.

Type:: str

summaries

list of LSA headers summarizing LSDB.

Type:: list[LSAHeader]

class sequence.network_management.routing_distributed.DistRoutingMessage(msg_type: DistRoutingMsgType, receiver: str, payload: HelloPayload | DBDPayload | LSRPayload | LSUPayload | LSAckPayload)

Message used by the distributed routing protocol.

msg_type

message type required by base message type.

Type:: Enum

receiver

name of destination protocol instance.

Type:: str

payload

message to be passed through destination network manager.

Type:: DistRoutingPayload

class sequence.network_management.routing_distributed.DistRoutingMsgType(*values): Enum class for message types used in distributed routing protocol.

class sequence.network_management.routing_distributed.DistributedRoutingProtocol(owner: QuantumRouter, name: str)

Class to implement distributed routing protocol (OSPF-like protocol).

owner

node that protocol instance is attached to.

Type:: Node

name

label for protocol instance.

Type:: str

lsdb

link state database.

Type:: LinkStateDB

fsm

mapping of all neighbors’ name to its FSM.

Type:: dict[str, NeighborFSM]

link_cost

mapping of neighbor name to link cost.

Type:: dict[str, float]

adj_cost

mapping of neighbor name with 2-way hellos to link cost.

Type:: dict[str, float]

seq_number

sequence number for own LSA.

Type:: int

refresh_enabled

whether refreshing own LSA is enabled.

Type:: bool

last_originated_time

time of last originated LSA.

Type:: int

check_neighbor_liveness(neighbor: str, last_hello_time: int)

Check if neighbor is still alive.

Parameters:

neighbor (str) – name of neighbor.
last_hello_time (int) – time of last hello received from neighbor.

dbd_retransmit(neighbor: str, dbd_msg: DistRoutingMessage)

Retransmit the DBD message when timeout.

Parameters:

neighbor (str) – name of neighbor.
dbd_msg (DistRoutingMessage) – the DBD message to be retransmitted.

ensure_fsm(neighbor: str) → NeighborFSM

Ensure FSM exists for a neighbor.

Parameters:: neighbor (str) – name of a neighbor.
Returns:: FSM for a neighbor.
Return type:: NeighborFSM

expire_lsa(last_originated_time: int)

Withdraw own LSA when it reaches max_age (if refresh is disabled).

Parameters:: last_originated_time (int) – the previous origin time of the LSA.

flood_to_all_neighbors(lsa: LSA, exclude_neighbor: str | None = None)

Flood LSA to all neighbors with 2-way adjacency.: An LSU message containing the LSA is sent to each neighbor, except the excluded neighbor if specified.

Parameters:

lsa (LSA) – LSA to be flooded.
exclude_neighbor (str | None) – neighbor to exclude from flooding.

get_age(item: LSA | LSAHeader) → int

Get age of LSA or LSAHeader.

Parameters:: item (LSA | LSAHeader) – LSA or LSAHeader.
Returns:: age of the item in picoseconds.
Return type:: int

handle_dbd(src: str, payload: DBDPayload)

Handle DBD message from the neighbor.: Request any missing or outdated LSAs.

Parameters:

src (str) – name of a source node.
payload (DBDPayload) – payload of a DBD message.

handle_hello(src: str, payload: HelloPayload)

Handle HELLO message from a neighbor.

Parameters:

src (str) – name of the source node.
payload (HelloPayload) – payload of HELLO message.

handle_lsack(src: str, payload: LSAckPayload)

Handle LSAck message from the neighbor.

Parameters:

src (str) – name of a source node.
payload (LSAckPayload) – payload of LSAck message.

handle_lsr(src: str, payload: LSRPayload)

Handle LSR message from a neighbor. Send back the requested LSAs.

Parameters:

src (str) – name of the source node.
payload (LSRPayload) – payload of LSR message.

handle_lsu(src: str, payload: LSUPayload)

Handle LSU message from a neighbor.

Parameters:

src (str) – name of source node.
payload (LSUPayload) – payload of LSU message.

init(): Initialize: 1) the FSM for each neighbor 2) the first hello event 3) the first LSA refresh event (enabled by default)

originate() → LSA

Originate and return its LSA, meanwhile increment its sequence number.

Returns:: the originated LSA.
Return type:: LSA

originate_and_flood(): Originate own LSA and flood to all neighbors with 2-way adjacency.

originate_withdrawal() → LSA: Originate a withdrawal LSA (MAX_AGE) for this router.

received_message(src: str, msg)

Receive the distributed routing message from another node.

Parameters:

src (str) – name of the source node.
msg (Message) – message received.

refresh_lsa(delay: int)

Refresh own LSA now via flooding, then schedule the next refresh after delay.

Parameters:: delay (int) – the delay (picoseconds) for sending the next refresh event.

run_spf() → dict[str, str]

Run Shortest Path First (SPF) algorithm to compute routing table.

Returns:: mapping of destination to next hop.
Return type:: forwarding_table (dict[str, str])

schedule_dbd_resend(neighbor: str, dbd_msg: DistRoutingMessage)

Schedule DBD retransmission (currently on for the master node, because the master initiates the exchange).

Parameters:

neighbor (str) – name of neighbor.
dbd_msg (DistRoutingMessage) – the DBD message to be retransmitted.

send_dbd(neighbor: str) → DistRoutingMessage

Send DBD message to neighbor.

Parameters:: neighbor (str) – name of neighbor.
Returns:: the DBD message sent.
Return type:: DistRoutingMessage

send_hello(delay: int)

Send HELLO message to all neighbors now,: and schedule the next send_hello after delay (picoseconds).

Parameters:: delay (int) – the delay (picoseconds) for sending the next send_hello event.

set_state(neighbor: str, new_state: str)

Set the state of the neighbor FSM.

Parameters:

neighbor (str) – name of neighbor.
new_state (str) – new state to set.

start_exstart(neighbor: str)

Start ExStart state with neighbor.: A master node is elected and begin DBD exchange.

Parameters:: neighbor (str) – name of neighbor.

update_forwarding_rule(dst: str, next_node: str)

Updates dst to map to next_node in forwarding table.: If dst not in forwarding table, add new rule.

Parameters:

dst (str) – name of destination node.
next_node (str) – name of next hop node.

class sequence.network_management.routing_distributed.HelloPayload(sender: str, seen_neighbors: set[str])

HELLO payload.

sender

name of sender node.

Type:: str

seen_neighbors

set of neighbors seen by sender.

Type:: set[str]

class sequence.network_management.routing_distributed.LSA(header: LSAHeader, links: list[Link])

Link State Advertisement. LS: who my neighbors are?

header

LSA header.

Type:: LSAHeader

links

list of links in this LSA.

Type:: list[Link]

class sequence.network_management.routing_distributed.LSAHeader(advertising_router: str, seq_number: int, originated_time: int)

Link State Advertisement header.

advertising_router

who originated the LSA, “this node”.

Type:: str

seq_number

sequence number of the LSA.

Type:: int

originated_time

time when LSA was originated.

Type:: int

class sequence.network_management.routing_distributed.LSAckPayload(sender: str, acks: list[tuple[str, int]])

Link State Acknowledgement payload.

sender

name of sender node.

Type:: str

acks

list of (advertising_router, seq_number) acknowledgements.

Type:: list[tuple[str, int]]

class sequence.network_management.routing_distributed.LSRPayload(sender: str, requested: list[str])

Link State Request payload.

sender

name of sender node.

Type:: str

requested

list of advertising routers whose LSAs are requested.

Type:: list[str]

class sequence.network_management.routing_distributed.LSUPayload(sender: str, lsas: list[LSA])

Link State Update payload.

sender

name of sender node.

Type:: str

lsas

list of LSAs being sent.

Type:: list[LSA]

class sequence.network_management.routing_distributed.Link(neighbor: str, cost: float)

Link information.

neighbor

neighbor node

Type:: str

cost

cost to neighbor

Type:: float

class sequence.network_management.routing_distributed.LinkStateDB

Link State Database for distributed routing protocol.

lsas

mapping of advertising router to LSA.

Type:: dict[str, LSA]

install(lsa: LSA, now: int) → bool

Install LSA into the database.

Parameters:

lsa (LSA) – LSA to be installed.
now (int) – current simulation time (picoseconds).

Returns:

True if LSA is new or updated, False otherwise.

Return type:

bool

purge_withdrawn(now: int) → list[str]

Purge withdrawn LSAs from the database.

Returns:: list of advertising routers whose LSAs are purged.
Return type:: list[str]

class sequence.network_management.routing_distributed.NeighborFSM(state: str = 'Down', last_hello_received: int = -1, pending_requested: set[str] = <factory>, master: bool = False, scheduled_dbd_resend_event: Event | None = None)

Finite State Machine for each neighbor.

STATES

Ordered OSPF neighbor states: - Down: no recent HELLOs seen - Init: HELLO seen from neighbor - TwoWay: mutual HELLOs (adjacency established) - ExStart: master/slave chosen, start DBD exchange - Exchange: DBD exchange in progress - Loading: requesting missing LSAs - Full: missing LSA all received, LSDBs synchronized

Type:: list[str]

state

the current state

Type:: str

last_hello_received

time of last hello received

Type:: int

pending_requested

which LSAs are requested but not yet received

Type:: set[str]

master

whether this node is master in DBD exchange

Type:: bool

scheduled_dbd_resend_event

scheduled DBD retransmission event for the master, to be canceled when receiving expected DBD from the slave or when neighbor goes down

Type:: Event

clear_scheduled_dbd_resend_event(): Reset the scheduled DBD retransmission events.

reset() → None: Fully reset the neighbor FSM to initial Down state.