mlsr/route/NamePrefixTable.go

// Package route
// @Author: Wang Feng
// @Description:
// @Version: 0.1.0
// @Date: 2022/6/10 11:16
// @Copyright: MIN-Group；国家重大科技基础设施——未来网络北大实验室；深圳市信息论与未来网络重点实验室
//

package route

import (
	"fmt"
	common2 "minlib/common"
	"minlib/component"
	"mlsr/lsa"
	"mlsr/lsdb"
	"mlsr/utils"
	"strconv"
)

//
//  NamePrefixTable
//  @Description: 名称前缀表
//
type NamePrefixTable struct {
	// 路由表池：存储“目的路由器标识URI->RTPE”的映射
	// 相当于存储了所有拥有前缀的路由表项，并包含每个路由表项对应的前缀列表信息，以及该前缀列表长度useCount
	m_rtpool map[string]*RoutingTablePoolEntry
	// 名称前缀表项列表
	nptEntryList []*NamePrefixTableEntry
	// 该名称前缀表所属的本机路由器标识
	m_ownRouterName *component.Identifier
	// 路由表。包含路由计算器计算出来的每个路由表标识及其对应的下一跳列表
	m_routingTable *RoutingTable

	// 信号接收器
	m_afterRoutingChangeConnection *utils.SignalConnection
	m_afterLsdbModified            *utils.SignalConnection

	// FIB FIB表交互结构体
	m_fib *Fib
}

//
//  PrintSelf
//  @Description: 打印名称前缀表的状态。用于测试。
//  @receiver t
//
func (t *NamePrefixTable) PrintSelf() {
	fmt.Println("------------------- Name Prefix Table begin: " + t.m_ownRouterName.ToUri() + "  -----------------")
	fmt.Println("-----------------" + " 1.路由表项池 begin " + "-----------------")
	fmt.Println("路由表项池大小：" + strconv.Itoa(len(t.m_rtpool)))
	for _, rtpe := range t.m_rtpool {
		fmt.Println(rtpe.ToString())
	}
	fmt.Println("-----------------" + " 1.路由表项池 end   " + "-----------------")
	fmt.Println("----------------" + " 2.名称前缀列表 start " + "----------------")
	fmt.Println("名称前缀列表大小：" + strconv.Itoa(len(t.nptEntryList)))
	for i := 0; i < len(t.nptEntryList); i++ {
		fmt.Println(t.nptEntryList[i].ToString())
	}
	fmt.Println("----------------" + " 2.名称前缀列表 end   " + "----------------")
	t.m_routingTable.PrintSelf()
	fmt.Println("------------------- Name Prefix Table end: " + t.m_ownRouterName.ToUri() + "    -----------------")
}

//
//  Init
//  @Description: 名称前缀表初始化
//  @receiver t
//  @param ownRouterName
//  @param routingTable
//  @param afterRoutingChangeSignal
//  @param afterLsdbModifiedSignal
//
func (t *NamePrefixTable) Init(ownRouterName *component.Identifier,
	routingTable *RoutingTable, afterRoutingChangeSignal *utils.Signal,
	afterLsdbModifiedSignal *utils.Signal, fib *Fib) {
	// 初始化数据结构
	t.m_rtpool = make(map[string]*RoutingTablePoolEntry)
	// 赋值变量
	t.m_ownRouterName = ownRouterName
	t.m_routingTable = routingTable
	t.m_fib = fib

	// 监听路由表的修改，触发NPT表修改
	bindRoutingChangeFunc := func(args ...interface{}) {
		common2.LogInfo("NamePrefixTable bindRoutingChangeFunc.")
		entrys, ok := args[0].([]*RoutingTableEntry)
		if !ok || entrys == nil {
			common2.LogError("NamePrefixTable Invalid Entry")
			return
		}
		t.UpdateWithNewRoute(entrys)
	}
	t.m_afterRoutingChangeConnection = afterRoutingChangeSignal.Connect(bindRoutingChangeFunc)

	// 监听LSDB修改，触发NPT表修改
	bindLsdbModifiedFunc := func(args ...interface{}) {
		common2.LogInfo("NamePrefixTable bindLsdbModifiedFunc.")
		// 获取四个参数
		ilsa := args[0].(lsa.ILsa)
		if ilsa == nil {
			common2.LogError("Invalid lsa")
			return
		}
		updateType := args[1].(lsdb.LsdbUpdate)
		common2.LogInfo("NamePrefixTable bindLsdbModifiedFunc lsa: ", ilsa.GetOriginRouter().ToUri())
		common2.LogInfo("NamePrefixTable bindLsdbModifiedFunc updateType: ", updateType)
		namesToAdd := []*component.Identifier{}
		namesToRemove := []*component.Identifier{}
		if updateType == lsdb.UPDATED {
			namesToAdd, ok := args[2].([]*component.Identifier)
			if !ok || namesToAdd == nil {
				common2.LogError("Invalid namesToAdd")
				return
			}
			namesToRemove, ok = args[3].([]*component.Identifier)
			if !ok || namesToRemove == nil {
				common2.LogError("Invalid namesToRemove")
				return
			}
		}
		// 执行更新操作
		t.UpdateFromLsdb(ilsa, updateType, namesToAdd, namesToRemove)
	}
	t.m_afterLsdbModified = afterLsdbModifiedSignal.Connect(bindLsdbModifiedFunc)
}

//
//  UpdateFromLsdb
//  @Description: 根据lsdb的更新，对名称进行增加、更新或移除
//  @receiver t
//  @param lsa
//  @param updateType
//  @param namesToAdd
//  @param namesToRemove
//
func (t *NamePrefixTable) UpdateFromLsdb(ilsa lsa.ILsa,
	updateType lsdb.LsdbUpdate, namesToAdd []*component.Identifier,
	namesToRemove []*component.Identifier) {
	// 如果是本地Lsa的增删更操作，则不做响应
	if ilsa.GetOriginRouter().ToUri() == t.m_ownRouterName.ToUri() {
		return
	}

	common2.LogInfo("Got update from Lsdb for router: ", ilsa.GetOriginRouter().ToUri())

	// lsa安装操作
	if updateType == lsdb.INSTALLED {
		// 先增加对该路由器标识的条目
		t.AddEntry(ilsa.GetOriginRouter(), ilsa.GetOriginRouter())

		// 只针对名称LSA进行更新
		if ilsa.GetType() == lsa.LsaNAMEType {
			// 获取该lsa中的名称前缀列表
			nlsa := ilsa.(*lsa.NameLsa)
			names := nlsa.GetNamePrefixes()
			// 遍历所有名称前缀，将其添加到名称前缀表中
			for i := 0; i < len(names); i++ {
				if names[i].ToUri() != t.m_ownRouterName.ToUri() {
					t.AddEntry(names[i], ilsa.GetOriginRouter())
				}
			}
		}
	} else if updateType == lsdb.UPDATED {
		// lsa更新操作（增加、删除）
		if ilsa.GetType() == lsa.LsaNAMEType {
			// 增加
			for i := 0; i < len(namesToAdd); i++ {
				if namesToAdd[i].ToUri() != t.m_ownRouterName.ToUri() {
					t.AddEntry(namesToAdd[i], ilsa.GetOriginRouter())
				}
			}
			// 删除
			for i := 0; i < len(namesToRemove); i++ {
				if namesToRemove[i].ToUri() != t.m_ownRouterName.ToUri() {
					t.RemoveEntry(namesToRemove[i], ilsa.GetOriginRouter())
				}
			}
		}
	} else {
		// 既不是安装，又不是更新（增加或删除lsa的某些部分） => 那就是删除整个LSA
		t.RemoveEntry(ilsa.GetOriginRouter(), ilsa.GetOriginRouter())
		if ilsa.GetType() == lsa.LsaNAMEType {
			// 获取该lsa中的名称前缀列表
			nlsa := ilsa.(*lsa.NameLsa)
			names := nlsa.GetNamePrefixes()
			// 遍历所有名称前缀，将其添加到名称前缀表中
			for i := 0; i < len(names); i++ {
				if names[i].ToUri() != t.m_ownRouterName.ToUri() {
					t.RemoveEntry(names[i], ilsa.GetOriginRouter())
				}
			}
		}
	}
}

//
//  findNamePrefix
//  @Description: 查找名称前缀
//  @receiver t
//  @param name
//  @return int 返回-1时表示没有查找到
//
func (t *NamePrefixTable) findNamePrefix(name *component.Identifier) int {
	for i := 0; i < len(t.nptEntryList); i++ {
		if t.nptEntryList[i].GetNamePrefix().ToUri() == name.ToUri() {
			return i
		}
	}
	return -1
}

//
//  deleteNamePrefix
//  @Description: 根据名称前缀的索引坐标，删除指定名称前缀
//  @receiver t
//  @param nameIndex
//
func (t *NamePrefixTable) deleteNamePrefix(nameIndex int) {
	var newList []*NamePrefixTableEntry
	for i := 0; i < len(t.nptEntryList); i++ {
		if i != nameIndex {
			newList = append(newList, t.nptEntryList[i])
		}
	}
	t.nptEntryList = newList
}

//
//  AddEntry
//  @Description: 此方法将路由器添加到名称前缀表条目中。如果名称前缀表条目不存在，则会创建它。
//    该方法将首先查看其缓存项的本地池，以找到destRouter的路由信息。
//    如果在那里找不到，它将构造一个，并用路由表中适当的RoutingTable条目中的信息填充它。
//    如果没有匹配项，它将实例化它，但没有下一跳。FIB也将收到NPT条目变更的通知。
//  @receiver t
//  @param name
//  @param destRouter
//
func (t *NamePrefixTable) AddEntry(name *component.Identifier, destRouter *component.Identifier) {
	// 检查播发的名称前缀是否已在表中。
	nameIndex := t.findNamePrefix(name)

	// 查找目的路由器标识是否在路由表项缓存池中
	v, ok := t.m_rtpool[destRouter.ToUri()]

	// 如果池中没有该目的路由器的路由表项，也即找不到去到name的路由路径，就加一个缓存池项
	if !ok {
		// 查看路由表，看是否有包含该目的路由器的条目
		rte := t.m_routingTable.FindRoutingTableEntry(destRouter)

		// 如果路由表里也没有，那我们在缓存里加一个新的条目（虽然没路径）
		rtpe := new(RoutingTablePoolEntry)
		if rte == nil {
			rtpe.InitDest(destRouter, 0)
		} else {
			// 有的话，直接从路由器中取出该条目，放入缓存池
			rtpe.InitRTE(rte, 0)
		}

		// 放入缓存池，并将v刷新为该缓存池项
		v = t.AddRtpeToPool(rtpe)
	}

	// 更新npt项，并通知给fib
	if nameIndex < 0 {
		// 如果NPT中没有该name
		common2.LogDebug("Adding origin: " + v.GetDestination().ToUri() +
			" to a new name prefix: " + name.ToUri())
		// 构造名称前缀表项，并添加之
		npte := new(NamePrefixTableEntry)
		npte.m_namePrefix = name
		npte.AddRoutingTableEntry(v) // useCount在这个时候会+1
		npte.GenerateNhlfromRteList()
		t.nptEntryList = append(t.nptEntryList, npte)
		nameIndex = t.findNamePrefix(name)

		// 如果这个条目有下一跳，我们需要通知FIB
		if len(npte.GetNextHops()) > 0 {
			common2.LogDebug("Updating FIB with next hops for ", npte.GetNamePrefix().ToUri())
			// 更新fib
			// m_fib.update(name, npte->getNexthopList());
			err := t.m_fib.Update(name, npte.GetNexthopList())
			if err != nil {
				common2.LogError(err.Error())
			}
		} else {
			// 如果没有下一跳
			// 路由表可以重新计算并添加一个没有下一跳的路由表条目，以替换现有的路由表条目。
			// 在这种情况下，通过下一个跃点无法再访问名称前缀，应将其从FIB中删除。
			// 但是，前缀应该保留在名称前缀表中，因为未来的路由表计算可能会添加下一跳。
			common2.LogDebug(npte.GetNamePrefix().ToUri() + " has no next hops; removing from FIB")
			// 更新fib
			// m_fib.remove(name);
			if err := t.m_fib.Remove(name); err != nil {
				common2.LogError(err.Error())
			}
		}
	} else {
		// 如果NPT有这个name
		common2.LogDebug("Adding origin: " + v.GetDestination().ToUri() +
			" to existing prefix: " + name.ToUri())
		// 更新之
		t.nptEntryList[nameIndex].AddRoutingTableEntry(v) // useCount在这个时候会+1
		t.nptEntryList[nameIndex].GenerateNhlfromRteList()

		// FIB通知
		if len(t.nptEntryList[nameIndex].GetNextHops()) > 0 {
			common2.LogDebug("Updating FIB with next hops for ",
				t.nptEntryList[nameIndex].GetNamePrefix().ToUri())
			// 更新fib
			//m_fib.update(name, npte->getNexthopList());
			if err := t.m_fib.Update(name, t.nptEntryList[nameIndex].GetNexthopList()); err != nil {
				common2.LogError(err.Error())
			}
		} else {
			common2.LogDebug(t.nptEntryList[nameIndex].GetNamePrefix().ToUri() +
				" has no next hops; removing from FIB")
			// 更新fib
			//m_fib.remove(name);
			if err := t.m_fib.Remove(name); err != nil {
				common2.LogError(err.Error())
			}
		}
	}

	// 将此NPT的引用添加到RTPE中。
	v.NamePrefixTableEntries[t.nptEntryList[nameIndex].GetNamePrefix().ToUri()] = t.nptEntryList[nameIndex]
}

//
//  RemoveEntry
//  @Description: 此方法从条目中删除目标。如果传递了无效的“名称-目标”对，也不会失败。
//    删除后，如果RoutingTablePoolEntry的使用计数为0，则会将其从表中删除。
//    此外，如果名称前缀没有与之关联的路由表条目，则会将其从NPT中删除。
//    在任何情况下，FIB都会被告知这些变化。
//  @receiver t
//  @param name
//  @param destRouter
//
func (t *NamePrefixTable) RemoveEntry(name *component.Identifier, destRouter *component.Identifier) {
	common2.LogDebug("Removing origin: " + destRouter.ToUri() + " from " + name.ToUri())

	// 根据目的路由器标识，获取其在路由条目缓存池中的条目
	rtpe, ok := t.m_rtpool[destRouter.ToUri()]
	if !ok {
		// 如果没有找到，则不进行后续处理
		common2.LogDebug("No entry for origin: " + destRouter.ToUri() +
			" found, so it cannot be removed from prefix: " + name.ToUri())
		return
	}

	// 查找名称前缀
	nameIndex := t.findNamePrefix(name)
	if nameIndex >= 0 {
		common2.LogDebug("Removing origin: " + rtpe.GetDestination().ToUri() +
			" from prefix: " + name.ToUri())

		// 判断该缓存表项在被删除一个与某前缀的关联之后，其使用数是否为零，如果是，则删除该引用。
		useCount := t.nptEntryList[nameIndex].RemoveRoutingTableEntry(rtpe)
		if useCount == 0 {
			t.DeleteRtpeFromPool(rtpe)
		}

		// 1 如果前缀是路由器前缀，并且没有任何其他路由表条目，则已从LSDB中删除与该原始路由器关联的邻接/坐标LSA，
		// 因此应从名称前缀表中删除路由器前缀。
		// 2 如果前缀是播发的名称前缀：如果另一个路由器播发此名称前缀，
		// 则RteList应具有该路由器的另一个条目；下一个跃点应重新计算并安装在FIB中。
		// 3 如果没有其他路由器播发此名称前缀，则RteList应为空，并且可以从名称前缀表中删除前缀。
		// 一旦新名称LSA播发此前缀，将创建前缀的新条目。
		if t.nptEntryList[nameIndex].GetRteListSize() == 0 {
			common2.LogDebug(name.ToUri() + " has no routing table entries;" +
				" removing from table and FIB")
			t.deleteNamePrefix(nameIndex)
			// 删除fib中的该name
			//m_fib.remove(name);
			if err := t.m_fib.Remove(name); err != nil {
				common2.LogError(err.Error())
			}
		} else {
			common2.LogDebug(name.ToUri() + " has other routing table entries;" +
				" updating FIB with next hops")
			t.nptEntryList[nameIndex].GenerateNhlfromRteList()
			// 更新fib
			//m_fib.update(name, (*nameItr)->getNexthopList());
			if err := t.m_fib.Update(name, t.nptEntryList[nameIndex].GetNexthopList()); err != nil {
				common2.LogError(err.Error())
			}
		}
	} else {
		common2.LogDebug("Attempted to remove origin: " + rtpe.GetDestination().ToUri() +
			" from non-existent prefix: " + name.ToUri())
	}
}

//
//  isNextHopsEqual
//  @Description: 遍历查看两个下一跳列表是否完全一致
//  @param hops1
//  @param hops2
//  @return bool
//
func isNextHopsEqual(hops1 []*NextHop, hops2 []*NextHop) bool {
	// 长度不等，则false
	if len(hops1) != len(hops2) {
		return false
	}
	// 遍历，如果有一个不相等，则false
	for i := 0; i < len(hops1); i++ {
		if hops1[i].LogicFaceUri() != hops2[i].LogicFaceUri() ||
			hops1[i].RouteCost.Cost() != hops2[i].RouteCost.Cost() {
			return false
		}
	}
	return true
}

//
//  UpdateWithNewRoute
//  @Description: 接收假定为详尽的条目列表，并使用条目中相应条目中包含的下一跳信息更新每个池条目。
//    如果找不到条目，则假定该池条目的目标不可访问，其下一跳信息将被删除。
//  @receiver t
//  @param entries
//
func (t *NamePrefixTable) UpdateWithNewRoute(entries []*RoutingTableEntry) {
	common2.LogDebug("Updating table with newly calculated routes")

	// 遍历名称前缀表中的路由表缓存池
	for _, rtpe := range t.m_rtpool {
		// 查看当前缓存表项的目的路由器，是否在传入的真路由表项里可以找到对应的
		sameIndex := -1 // 默认没找到
		for i := 0; i < len(entries); i++ {
			if entries[i].GetDestination().ToUri() == rtpe.GetDestination().ToUri() {
				sameIndex = i
			}
		}

		// 根据缓存池与原路由表项的差异，将缓存池更新
		if sameIndex >= 0 && !isNextHopsEqual(rtpe.GetNextHops(), entries[sameIndex].GetNextHops()) {
			// 如果找到了对应条目，且两个路由表条目的下一跳列表不一致
			common2.LogDebug("Routing entry: " + rtpe.GetDestination().ToUri() + " has changed next-hops.")
			// 更新rtpe的下一跳列表
			rtpe.SetNexthopList(entries[sameIndex].NextHopList)
			// 更新rtpe的每个名称前缀表项
			for _, nameEntry := range rtpe.NamePrefixTableEntries {
				t.AddEntry(nameEntry.GetNamePrefix(), rtpe.GetDestination())
			}
		} else if sameIndex < 0 {
			// 没有找到对应条目，说明到该路由器的路径已经无了无了无了~
			common2.LogDebug("Routing entry: " + rtpe.GetDestination().ToUri() + " now has no next-hops.")
			// 更新rtpe的下一跳列表：清空
			rtpe.Clear()
			// 更新rtpe的每个名称前缀表项
			for _, nameEntry := range rtpe.NamePrefixTableEntries {
				t.AddEntry(nameEntry.GetNamePrefix(), rtpe.GetDestination())
			}
		} else {
			// 有找到对应条目，但是两个条目的下一跳列表完全一致
			common2.LogDebug("No change in routing entry:" + rtpe.GetDestination().ToUri() +
				", no action necessary.")
		}
	}
}

//
//  AddRtpeToPool
//  @Description: 将RoutingTablePoolEntry添加到NPT的本地池。
// 在C++版实现中，返回值将使用共享指针，因为它消除了处理生命周期问题的复杂hacks，并简化了内存管理。
//  @receiver t
//  @param rtpe
//  @return *RoutingTablePoolEntry
//
func (t *NamePrefixTable) AddRtpeToPool(rtpe *RoutingTablePoolEntry) *RoutingTablePoolEntry {
	t.m_rtpool[rtpe.GetDestination().ToUri()] = rtpe
	return rtpe
}

//
//  DeleteRtpeFromPool
//  @Description: 从池中删除池项。
//  @receiver t
//  @param rtpe
//
func (t *NamePrefixTable) DeleteRtpeFromPool(rtpe *RoutingTablePoolEntry) {
	// 查看是否有该条目
	_, ok := t.m_rtpool[rtpe.GetDestination().ToUri()]
	if !ok {
		common2.LogDebug("Attempted to delete non-existent origin: " +
			rtpe.GetDestination().ToUri() + " from NPT routing table entry storage pool.")
	}
	delete(t.m_rtpool, rtpe.GetDestination().ToUri())
}