-
Notifications
You must be signed in to change notification settings - Fork 0
/
bridge.py
executable file
·274 lines (236 loc) · 11.2 KB
/
bridge.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
import time
import copy
#class which represents a config message for spanning tree algorithm
class Message:
def __init__(self, b_id, root, d, port):
self.bridge_id = b_id
# the bridge which it came from
self.root = root
# supposed root
self.d = d
# distance of sending bridge
self.port = port
def __repr__(self):
return 'Bridge:{} Root:{} D:{} Port:{}'.format(self.bridge_id, self.root, self.d, self.port)
def compare(self, other, current_closest_to_root):
# compare 2 given message with self and return 1 if input is 'better'
# 'better' is defined acc to the rules discussed in class
cond1 = (other.root < self.root)
cond2 = (other.root == self.root and other.d < self.d)
cond3 = (other.root == self.root and other.d == self.d and other.bridge_id < current_closest_to_root)
if cond1 or cond2 or cond3:
return 1
else:
return 0
#class which represents a LAN segment
class LAN:
def __init__(self, name):
self.name = name
self.host_list = []
# is_dp - designated port
self.bridge_dict = {}
# stores messages and forwards to all bridges connected to self except source
# sender appends messages to this list
self.to_forward = []
def add_bridge(self, bridge_id, is_dp=0):
self.bridge_dict[bridge_id] = is_dp
def time_step(self, t):
# forward each received message to non-sender bridge
to_return = {k: [] for k in self.bridge_dict.keys()}
empty = True
for message in self.to_forward:
for bridge_id in self.bridge_dict.keys():
if bridge_id != message.bridge_id:
# to_return is a dict with keys as receiver
to_return[bridge_id].append(copy.copy(message))
empty = False
# empty queue
self.to_forward = []
# print('LAN generated messages for id', self.name, to_return)
return to_return, empty
#class which represents a bridge
class Bridge:
def __init__ (self, bridge_id):
self.id = bridge_id
self.port_dict = {}
self.forwarding_table = {}
# parameters which are changed acc by spanning tree algo
self.root_prediction = self.id
self.distance_from_root = 0
self.closest_to_root_bridge = self.id
# list of messages sent by connected LAN segments
self.received_messages = []
# store best message received on each port
self.current_best_on_port = {}
# global best
self.current_overall_best = Message(self.id, self.id, 0, -1)
def add_port(self, port_name, port_type='DP'):
self.port_dict[port_name] = port_type
self.current_best_on_port[port_name] = None
# update best message on port
def update_port_local_best(self, port, message):
if self.current_best_on_port[port] is None or self.current_best_on_port[port].compare(message, self.current_best_on_port[port].bridge_id):
self.current_best_on_port[port] = copy.copy(message)
# update global best
def update_best(self, m):
self.root_prediction = m.root
self.distance_from_root = m.d+1
self.closest_to_root_bridge = m.bridge_id
# print("***Updating bridge {} with message {}***".format(self.id, m))
self.current_overall_best = Message(self.id, self.root_prediction, self.distance_from_root, -1)
# called at each clock tick
def time_step(self, t, trace):
# lan segments connected to bridge - keys, values - list of values to be forwarded
to_return = {k: [] for k in self.port_dict.keys()}
#messages to dump on LAN seg,ent
empty = True
new_best = False
# update own config with recived messages
for message in self.received_messages:
p = message.port
self.update_port_local_best(p, message)
message.d += 1
# if received message is better than global best, update
if self.current_overall_best.compare(message, self.closest_to_root_bridge):
# update_best also increments d while copying into bridge attributes
message.d -= 1
self.update_best(message)
message.d += 1
new_best = True
# print trace
if trace:
print("{} r {} ({} {} {})".format(t, self.id, message.root, message.d-1, message.bridge_id))
# forward messages
for port, port_type in self.port_dict.items():
# construct message to forward
to_forward = Message(self.id, self.root_prediction, self.distance_from_root, port)
# cur best is local best for that port
cur_best = self.current_best_on_port[port]
if cur_best is not None:
# conditions for root port
rp_cond = self.root_prediction == cur_best.root and \
self.distance_from_root-1 == cur_best.d and \
self.closest_to_root_bridge == cur_best.bridge_id
# conditions for null port - REVIEW LATER!!!!
np_cond = (self.root_prediction == cur_best.root and \
self.distance_from_root-1 == cur_best.d and \
self.closest_to_root_bridge < cur_best.bridge_id) or \
(self.root_prediction == cur_best.root and \
self.distance_from_root == cur_best.d and \
self.id > cur_best.bridge_id)
else:
# if receiving message on that port for th first time, bridge assumes it is the DP
rp_cond = False
np_cond = False
dp_cond = cur_best is None or cur_best.compare(to_forward, self.id)
# DP - root port problems
if dp_cond:
# forward messages only if the configuration was a new global best
if new_best:
to_return[port].append(to_forward)
if trace:
print("{} s {} ({} {} {})".format(t, self.id, to_forward.root, to_forward.d, to_forward.bridge_id))
self.current_best_on_port[port] = to_forward
self.port_dict[port] = 'DP'
# RP
elif rp_cond:
self.port_dict[port] = 'RP'
elif np_cond:
self.port_dict[port] = 'NP'
# generate own config if root and at t=0 ONLY
if self.root_prediction == self.id and t <= 0:
# print('Generating config message: {}'.format(self.id))
for port_name in self.port_dict.keys():
m = Message(self.id, self.id, 0, port_name)
to_return[port_name].append(m)
self.update_port_local_best(port_name, m)
empty = False
# empty the queue
self.received_messages = []
# print('Bridge generated messages for id', self.id, to_return)
return to_return, empty
def __repr__(self):
s = ''
s += 'Bridge id: {}\n'.format(self.id)
s += 'Root Pred: {} and Dist from root: {}\n'.format(self.root_prediction, self.distance_from_root)
s += 'Port Dict: {}'.format(self.port_dict)
return s
def pretty_print(self):
s = self.id + ': '
for port_name in sorted(self.port_dict.keys()):
s += "{}-{} ".format(port_name, self.port_dict[port_name])
return s[:-1]
#class for creating an internal representation of a topology
class Topology:
def __init__ (self):
self.bridge_dict = {}
#maintains a list of lans connected to each bridge
self.lan_dict = {}
#maintains a list of bridges associated with a LAN
self.pending_messages = []
def add_bridge(self, bridge):
self.bridge_dict[bridge.id] = bridge
# add bridge to LAN dictionary
for port_name, port_type in bridge.port_dict.items():
if port_name not in self.lan_dict.keys():
self.lan_dict[port_name] = LAN(port_name)
self.lan_dict[port_name].add_bridge(bridge.id)
def add_hosts(self, lan_seg, host_list):
for port_name in self.lan_dict.keys():
if port_name==lan_seg:
self.lan_dict[port_name].host_list = host_list
# called at each clock tick
def time_step(self, t, trace):
lan_messages = []
# lan_messages contains all messages which bridges have generated
stop = True
for bridge in self.bridge_dict.values():
# m is the dict containing LAN as keys and the messages to be dumped as values
m, empty = bridge.time_step(t, trace)
lan_messages.append(m)
if not empty:
stop = False
# dump the generated bridge messages into the LAN segment's list
for lan_message_dict in lan_messages:
for lan_name, messages in lan_message_dict.items():
self.lan_dict[lan_name].to_forward += messages
# get messages forwarded by LAN segment
bridge_messages = []
for lan in self.lan_dict.values():
m, empty = lan.time_step(t)
bridge_messages.append(m)
if not empty:
stop = False
# pass on LAN segment messages to bridge
for bridge_message_dict in bridge_messages:
for bridge, messages in bridge_message_dict.items():
self.bridge_dict[bridge].received_messages += messages
return stop
def __repr__(self):
s = ''
for bridge_id in sorted(self.bridge_dict.keys()):
s += self.bridge_dict[bridge_id].pretty_print() + '\n'
return s[:-1] # remove last newline
#transfers messages from a sender lan to next hop, recursively called on all hops
def message_send(topology, sender_lan, receiver_lan, sender, sending_lans, receiver, t, trace):
sending_bridges = []
#maintain all the next hops that the message has to be sent to
sending_lans.append(sender_lan.name)
for i in topology.lan_dict[sender_lan.name].bridge_dict.keys():
if(topology.bridge_dict[i].port_dict[sender_lan.name] != 'NP'):
sending_bridges.append(topology.bridge_dict[i])
for i in sending_bridges:
if sender not in i.forwarding_table.keys():
i.forwarding_table[sender] = sender_lan.name
if receiver not in i.forwarding_table.keys():
for j in (topology.bridge_dict[i.id].port_dict.keys()):
if(topology.bridge_dict[i.id].port_dict[j]!='NP'):
if j not in sending_lans:
sender_lan2 = topology.lan_dict[j]
message_send(topology, sender_lan2, receiver_lan, sender, sending_lans, receiver, t+1, trace)
else:
#case where receiver is already in the forwarding table
sender_lan2 = topology.lan_dict[i.forwarding_table[receiver]]
if(sender_lan2.name not in sending_lans):
# print(sender_lan2.name)
message_send(topology, sender_lan2, receiver_lan, sender, sending_lans, receiver, t+1, trace)